Shortening codes

Your task is to change number n from decimal to in base-p positional notation.

Input

The first line of the standard input contains one integer t (t<10001) which is the number of test cases.

In each of the next t lines there are two numbers: n<22*10⁸ and p<17 (n - number in decimal, p - base in which you should print number n).

Output

For each test, print number n in base-p positional notation.

Example

Input:
7
4 5
4 3
4 2
4 4
12 16
123 10
123 13

Output:
4
11
100
10
c
123
96