問題文

$T$ 個の非負整数 $N_1,\dots N_T$ を $B$ 進数に変換してください。
ただし、$B$ は、$-10$ 以上 $-2$ 以下の負の整数です。

$B$ 進数$M$ 桁で $a_{M-1}{a}_{M-2}\dots a_1{a}_0$ と表される数は、
$a_{M-1}\times B^{M-1}+a_{M-2}\times B^{M-2}+\cdots +a_1\times B^1+a_0\times B^0$ です。
このルールを $B$ が負の整数の場合にも拡張して $B$ 進数に変換してください。

例えば $-3$ 進数 $5$ 桁で $20021$ と表される数は、
$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$
です。つまり $157$ の $-3$ 進数表現は、$20021$ です。

出力する $B$ 進数表現の先頭には、冗長なゼロを付与してはいけません。
後述のサンプル1の最初の例では、10011だけが正解であり、010011や0010011は不正解です。
なお、整数の $B$ 進数表現は、先頭の冗長なゼロを除き一意になることが保障されています。

入力

$T$ $B$
$N_1$
$N_2$
$⋮$
$N_T$

$T,B,N_1\dots N_T$ は $10$ 進数表記。
$1\le T\le 10000$
$-10\le B\le -2$
$0\le N_i\le {10}^9$
入力は全て整数

出力

$T$ 行に分けて、$N_1$ から $N_T$ を $B$ 進数で表したときの表現を出力してください。

サンプル

5 -2
15
1
5
6
8

10011
1
101
11010
11000

5 -3
15
1
5
6
8

210
1
122
110
112