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}\)