Sinan is studying base arithmetic at his math course. His teacher, promises him a candy for each given number to be rewritten in the base \(\mathbf{K}\). Sinan wants all the candies and for that, he needs your help.

For a number to be rewritten in the base \(\mathbf{K}\):

\(\mathbf{N = a_n \cdot K^n + a_{n-1} \cdot K^{n-1} + ... + a_1 \cdot K^1 + a_0 \cdot K^0}\)

Sinan needs to write the numbers as a series consists of \(\mathbf{a_i}\)'s without unnecessary 0's at the beginning for candies.

Input

The first line consists of integer \(\mathbf{q}\).

Next \(\mathbf{q}\) lines will contain integers \(\mathbf{N_i}\) and \(\mathbf{K_i}\).

Batch #1:

• \(1 \leq \mathbf{q} \leq 100\)
• \(1 \leq \mathbf{N_i} \leq 100\)
• \(2 \leq \mathbf{K_i} \leq 10\)

Batch #2:

• \(1 \leq \mathbf{q} \leq 10^{4}\)
• \(1 \leq \mathbf{N_i} \leq 10^{18}\)
• \(2 \leq \mathbf{K_i} \leq 10\)

Output

Print \(\mathbf{q}\) lines. Each line should contain \(\mathbf{N_i}\) in base \(\mathbf{K_i}\), the list of \(\mathbf{A}\).

Samples

Input:

2
5 2
7 3

Output:

101
21

Input:

3
25 10
25 4
25 3

Output:

25
121
221

Explanation

1. Output

• \(\mathbf{5 = 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0}\)
• \(\mathbf{7 = 2 \cdot 3^1 + 1 \cdot 3^0}\)