题目描述

小 C 做了一台「进制翻译机」：输入一个 $a$ 进制的非负整数 $s$，翻译机会把它改写成 $b$ 进制输出。

数字的写法约定如下：$0 \sim 9$ 用 0 ~ 9 表示，$10 \sim 15$ 用大写字母 A ~ F 表示。除了数 $0$ 本身写作 0 以外，任何数都没有前导零。

现在有 $q$ 次翻译请求，请你依次输出翻译结果。

输入格式

第一行一个整数 $q$，表示翻译请求的次数。

接下来 $q$ 行，每行先是一个整数 $a$，然后是一个 $a$ 进制数 $s$，最后是一个整数 $b$，用空格分隔。

输出格式

共 $q$ 行，每行一个 $b$ 进制数，表示对应请求的翻译结果。

样例 #1

样例输入 #1

3
10 255 16
16 FF 2
2 0 8

样例输出 #1

FF
11111111
0

样例解释

• 十进制的 $255 = 15 \times 16 + 15$，写成十六进制是 FF；
• 十六进制的 FF 就是十进制的 $255 = 2^8 - 1$，写成二进制是 $8$ 个 1；
• $0$ 在任何进制下都写作 0。

提示

数据范围

记 $v$ 为 $s$ 所表示的数的大小。

• 对于 $30\%$ 的数据：$a = 10$，$v \le 10^9$；
• 对于 $60\%$ 的数据：$v < 2^{31}$；
• 对于 $100\%$ 的数据：$1 \le q \le 1000$，$2 \le a, b \le 16$，$0 \le v \le 10^{18}$，$s$ 是合法的 $a$ 进制数。

提示

• 可以先把 $s$ 从 $a$ 进制转成十进制，再用「除基取余、倒序排列」转成 $b$ 进制。
• $10^{18}$ 远远超过了 int 的范围，请使用 long long。