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