Bajtosiaは最近掛け算を習い、その掛け算がとても気に入りました。

彼女は次のような「数字の掛け算遊び」を考えました。まず、黒板に正の整数 $x$ を書きます。次に、その数の各桁の数字（十進法）を掛け合わせ、得られた結果で元の $x$ を置き換えます。この手順を、$x$ が一桁の数になるまで繰り返します。一回の遊びは、その一桁の数で終了します。どのような初期値 $x$ から始めても、この遊びは必ず終了することが証明できます。

例えば、$x = 57$ から遊びを始めるとします。最初のステップで、Bajtosia は $5 \cdot 7 = 35$ という数に移ります。次のステップで $3 \cdot 5 = 15$ に移り、最後のステップで $1 \cdot 5 = 5$ に移ります。この数は一桁なので、遊びは数字 $5$ で終了します。

一方、もし初期値が $x = 255$ であれば、最初のステップで $2 \cdot 5 \cdot 5 = 50$ となり、次のステップで $5 \cdot 0 = 0$ となります。遊びは数字 $0$ で終了します。

幼稚園から帰ってきた Bajtosia は、連続する値から始めてこの掛け算遊びを行います。 1回目の遊びは $x = 1$ から始まり、数字 $1$ で終了します。 2回目の遊びは $x = 2$ から始まり、数字 $2$ で終了します。 ... 10回目の遊びは $x = 10$ から始まり、数字 $0$ で終了します。 11回目の遊びは $x = 11$ から始まり、数字 $1$ で終了します。 ... 56回目の遊びは $x = 56$ から始まり、数字 $0$ で終了します。 57回目の遊びは $x = 57$ から始まり、数字 $5$ で終了します。 * ...

$t$ 日間にわたり、Bajtosia は幼稚園から帰ってくるとこのような数字の掛け算遊びの列を開始し、毎日飽きるまで遊びました。具体的には、$i$ 日目に Bajtosia は $n_i$ 回の掛け算遊びを行い、最後の遊びは $x = n_i$ から開始しました。

各日について、$n_i$ が与えられたとき、0 から 9 までの各数字について、その数字で終了した掛け算遊びが何回あったかを求めてください。

入力

1行目には、Bajtosia が数字の掛け算遊びを行った日数 $t$ ($1 \le t \le 1000$) が与えられます。

2行目には、$t$ 個の整数 $n_1, n_2, \dots, n_t$ ($1 \le n_i \le 10^{18}$) が与えられ、それぞれ各日に Bajtosia が行った遊びの回数を表します。

出力

$t$ 行を出力してください。各行には、その日に終了した掛け算遊びの結果が数字 $0, 1, \dots, 9$ であった回数を順に、10個の整数で出力してください。

入出力例

入力 1

5
10 56 57 123 1

出力 1

1 1 1 1 1 1 1 1 1 1
11 2 7 3 6 5 8 2 9 3
11 2 7 3 6 6 8 2 9 3
36 3 11 4 12 8 16 4 24 5
0 1 0 0 0 0 0 0 0 0