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