statement.md

n進数

Problem Statement

日常、我々は数として10進数に多く触れている。一方で、コンピュータの世界では2進数や16進数などが多く使われる。例えば、10進数における5は2進数で表すと101であるし、10進数における140は16進数で表すと8Cである。

10進数で表された数を、指定された基数(n進数でいうところのn)に変換したとき、どう表されるか求めよ。

Input

入力は以下の形式で表される。

N
B₁ T₁
B₂ T₂
:
B_N T_N

ここでNはデータセットの個数、Bは変換すべき基数、Tは変換元となる10進数の数である。

Constraints

入力は以下の条件をすべて満たす。

• 1 <= N <= 100
• 1 <= i <= N を満たすすべての整数iについて、
  • 2 <= B_i <= 32
  • 1 <= T_i <= 1,000,000,000

Output

出力は、変換後の数値を1行で出力せよ。

Note

• この問題の制約上、出力は最大でも30文字を超えない。
• 基数が11以上の場合、各桁に利用する数値は0〜9および下記の表のように大文字のアルファベットを用いよ。

文字	A	B	C	D	E	F	G	H	I	J	K
表す数値(10進数)	10	11	12	13	14	15	16	17	18	19	20

文字	L	M	N	O	P	Q	R	S	T	U	V
表す数値(10進数)	21	22	23	24	25	26	27	28	29	30	31

Sample Input 1

2
2 5
16 140

Sample Output 1

101
8C

問題文にも示した通り、10進数における5は2進数では101、10進数における140は16進数では8Cと表される。

Sample Input 2

4
16 43
3 73
11 42
32 32582057

Sample Output 2

2B
2201
39
V2AD9