Alien Base Conversion

Aliens on one planet have sixteen fingers, so they write numbers with sixteen digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, in ascending order). Just like our decimal system, a number is written as a sequence of digits, and its value follows these rules:

• The value of a single-digit number is the value of that digit.
• The value of a number formed by a number b followed by a digit d is the value of b times a fixed base, plus the value of d. In decimal the base is ten; for these sixteen-fingered aliens the base is sixteen.

Aliens on other planets have different numbers of fingers. They follow the same rules for writing numbers, but each uses a different base.

To help these aliens communicate, write a program that translates a number written by one alien into the number understood by another alien.

The first line contains a single integer, the number of test cases that follow.

Each test case is a single line with three values x, y, and z. Both x and y are written in decimal and are the bases used by the two aliens; each is at least $2$ and at most $36$. The number z is written in base x, using the digits 0-9 and the uppercase letters A-Z for the digit values 10 through 35. The value of z is at most four billion.

For each test case, output a single line containing the number equal in value to z but written in base y.

Use the digits 0-9 and the uppercase letters A-Z (for values 10 through 35), with no leading zeros (the value zero is written as a single 0).