Problem Statement

Convert $T$ non-negative integers $N_1, \dots N_T$ to base $B$.
Here, $B$ is a negative integer between $-10$ and $-2$, inclusive.

The number represented in base $B$ with $M$ digits as $a_{M-1} a_{M-2} \dots a_1 a_0$ is
$a_{M-1} \times B^{M-1} + a_{M-2} \times B^{M-2} + \dots + a_1 \times B^1 + a_0 \times B^0$.
Extend this rule to the case where $B$ is a negative integer, and convert the numbers to base $B$.

For example, the number represented in base $-3$ with $5$ digits as $20021$ is
$2 \times (-3)^4 + 0 \times (-3)^3 + 0 \times (-3)^2 + 2 \times (-3)^1 + 1 \times (-3)^0$
$= 2 \times 81 + 0 \times (-27) + 0 \times 9 + 2 \times (-3) + 1 \times 1$
$= 162 + 0 + 0 + (-6) + 1$
$= 157$
. That is, the base $-3$ representation of $157$ is $20021$.

The base $B$ representation you output must not have redundant leading zeros.
In the first case of Sample 1 below, only 10011 is correct, and 010011 and 0010011 are incorrect.
It is guaranteed that the base $B$ representation of an integer is unique, apart from redundant leading zeros.

Input

$T$ $B$
$N_1$
$N_2$
$\vdots$
$N_T$

$T, B, N_1 \dots N_T$ are written in base $10$.
$1 \le T \le 10000$
$-10 \le B \le -2$
$0 \le N_i \le 10^9$
All input values are integers.

Output

Output the base $B$ representations of $N_1$ through $N_T$ on $T$ separate lines.

Sample

5 -2
15
1
5
6
8

10011
1
101
11010
11000

5 -3
15
1
5
6
8

210
1
122
110
112