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 ~Q~ queries, convert a base ~b_1~ number, ~n~, to base ~b_2~.

Since Max knows you are a great programmer, Max has asked you to help him.

Can you help Max solve his V-Buck crisis?

Constraints

~1 \le Q \le 10^5~

~2 \le b_1, b_2 \le 10~

~1 \le n_{10} \le 10^9~

Note that ~n_{10}~ represents ~n~ in base ~10~.

Subtask 1 [30%]

~b_1~ and ~b_2~ are each either ~2~ or ~10~.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain ~Q~, the number of queries.

The next ~Q~ lines will contain ~b_1~, ~n~, and ~b_2~, the current base of the number, the number in that base, and the next base of the number, respectively.

Output Specification

Output ~Q~ lines, the number converted from base ~b_1~ to base ~b_2~.

Note that there should be no leading zeroes after converting.

Sample Input 1

2
2 101 10
10 64 2

Sample Output 1

5
1000000

Sample Input 2

2
3 22 10
10 6 4

Sample Output 2

8
12