题目描述

阿明需要将每件商品的十进制编号转换为指定进制的字符串。

第 $i$ 件商品的原始编号为 $N_i$，目标货架的进制为 $B_i$，其中 $2 \le B_i \le 36$。

阿明只处理非负整数，且标签中不允许出现负号。若编号为 $0$，则标签仅输出 0。

请你帮助阿明计算每件商品在对应进制下的编号字符串。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例数量。

接下来 $t$ 行，每行包含两个整数 $N$ 和 $B$：

• $0 \le N \le 10^{18}$
• $2 \le B \le 36$

其中，$N$ 表示十进制原始编号，$B$ 表示目标进制。

输出格式

对于每个测试用例，输出一行字符串，表示 $N$ 的 $B$ 进制表示。

其中：

• 数值 $0 \sim 9$ 用字符 0 到 9 表示；
• 数值 $10 \sim 35$ 用大写字母 A 到 Z 表示。

样例输入

3
255 16
123 2
0 36

样例输出

FF
1111011
0