题目描述

将 $\red{p}$进制 $\red{n}$ 转换为 $\red{q}$ 进制。

$\red{p}$ 和 $\red{q}$ 的取值范围为[$\red{2，36}$]，

其中，用到的数码按从小到大依次为：0，1，2，3，4，5，6，7，8，9，A，B，...，Z，不考虑小写字母。

输入格式

一共1+m 行： 第1行为 $\red{m}$，表示后面有 m 行（$\red{1 <= m <= 60}$）.

其后的m行中， 每行$\red{3}$个数: 进制$\red{p}$，$\red{p}$进制数$\red{n}$，以及进制 $\red{q}$。

三个数之间用逗号间隔。

$\red{n}$ 的长度不超过$\red{50}$位。

输出格式

转换后的 $\red{q}$ 进制数。

样例

输入样例

6
18,2345678A123,18
15,23456,18
12,2345678,20
16,12345678,23
25,3456AB,21
18,AB1234567,22

输出样例

2345678A123
114E0
22B7A4
21A976L
7C2136
22JF0G367