Given a number n in a number system with base a, convert it to a number in base b.

Let's say the digits available to us are 0 to 9 and characters A to Z (capital letters). A to Z correspond to digits 10 to 35 respectively. Now a number system with base X has digits from 0 till X-1. First line of input will contain a number T = no. of test cases. Next T lines will each contain a test case with 3 numbers n,a and b separated by space. n is a number (given as string) in base a and it needs to be converted to base b.

For each test case, convert the number n from base a to b and print the output on a single line.

6
0 2 3
512 10 16
10 2 10
45A 12 4
FCDS 36 5
255 10 16

0
200
2
22012
140402023
FF