Number Base Conversion

You are given a number represented in base \(B_1\) and you are required to convert it to a number in base \(B_2\). The number is given as a string, using digits 0-9 and uppercase letters A-Z for values beyond 9. It is guaranteed that \(2 \leq B_1, B_2 \leq 36\), and the string representation is valid in base \(B_1\).

Your task is to write a program that reads \(T\) test cases. For each test case, you should convert the given number from base \(B_1\) to base \(B_2\) and output its representation. Ensure that you output the result in uppercase letters. When the number is 0, the output should be "0".

Note: The conversion process includes converting the number from base \(B_1\) to base 10, and then from base 10 to base \(B_2\). Ensure the algorithm works efficiently for multiple test cases.

inputFormat

The input begins with a line containing an integer \(T\), representing the number of test cases. Each of the following \(T\) lines contains three values separated by spaces:

• An integer \(B_1\): the source base.
• A string \(S\): the representation of the number in base \(B_1\).
• An integer \(B_2\): the target base.

It is guaranteed that \(2 \leq B_1, B_2 \leq 36\) and that \(S\) is a valid number in base \(B_1\).

outputFormat

For each test case, output a single line with the representation of the number in base \(B_2\). The output should be in uppercase letters and without any extra spaces or newlines.

## sample

1
10 5 2

101

</p>