Having spent his last V-Buck, Max was upset, so Bob Xiong decided to cheer him up.
Bob told Max that he would buy him a Fortnite skin if he could solve this problem:
Given queries, convert a base number, , to base .
Since Max knows you are a great programmer, Max has asked you to help him.
Can you help Max solve his V-Buck crisis?
Note that represents in base .
Subtask 1 [30%]
and are each either or .
Subtask 2 [70%]
No additional constraints.
The first line will contain , the number of queries.
The next lines will contain , , and , the current base of the number, the number in that base, and the next base of the number, respectively.
Output lines, the number converted from base to base .
Note that there should be no leading zeroes after converting.
Sample Input 1
2 2 101 10 10 64 2
Sample Output 1
Sample Input 2
2 3 22 10 10 6 4
Sample Output 2