Submit solution

Points:
5 (partial)

Time limit:
1.0s

Java
1.5s

Memory limit:
256M

Author:

Problem type

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?

#### Constraints

Note that represents in base .

##### Subtask 1 [30%]

and are each either or .

##### Subtask 2 [70%]

No additional constraints.

#### Input Specification

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 Specification

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

```
5
1000000
```

#### Sample Input 2

```
2
3 22 10
10 6 4
```

#### Sample Output 2

```
8
12
```

## Comments