Description

Convert the decimal input number N (0 ≤ N ≤ 2 147 483 647) into a base B number (2 ≤ B ≤ 9).

Input

First, the number T of test cases is given. Each test case is specified by the numbers N and B, separated by space.

Output

The converted number. The result for each test case should be printed in a separate line.

Sample Input

5

7 2

4 2

4 3

4 4

1464724260 7

Sample Output

111

100

11

10

51203644056