Bajtosia 最近學會了乘法，並且非常喜歡這個運算。

她發明了一個數字乘法遊戲。她先在黑板上寫下一個正整數 $x$。接著，她將該數的各位數字（在十進位制下）相乘，並用所得的結果取代舊的 $x$ 值。她重複這個步驟，直到 $x$ 變成一個個位數為止。單次乘法遊戲便以該個位數結束。可以證明，無論初始值 $x$ 為何，遊戲總會結束。

例如，遊戲可以從 $x = 57$ 開始。第一步後，Bajtosia 得到 $5 \cdot 7 = 35$。下一步得到 $3 \cdot 5 = 15$，最後一步得到 $1 \cdot 5 = 5$。因為 $5$ 是一個個位數，所以遊戲以數字 $5$ 結束。

另一方面，如果初始數字為 $x = 255$，則第一步 Bajtosia 會得到 $2 \cdot 5 \cdot 5 = 50$，第二步得到 $5 \cdot 0 = 0$。遊戲將以數字 $0$ 結束。

從幼兒園回來後，Bajtosia 開始進行這些乘法遊戲，並且總是從連續的數值開始： 第一場遊戲從 $x = 1$ 開始，並立即以數字 $1$ 結束。 第二場遊戲從 $x = 2$ 開始，並立即以數字 $2$ 結束。 ... 第十場遊戲從 $x = 10$ 開始，並以數字 $0$ 結束。 第十一場遊戲從 $x = 11$ 開始，並以數字 $1$ 結束。 ... 第五十六場遊戲從 $x = 56$ 開始，並以數字 $0$ 結束。 第五十七場遊戲從 $x = 57$ 開始，並以數字 $5$ 結束。 * ...

在接下來的 $t$ 天裡，Bajtosia 每天從幼兒園回來後都會進行這樣的一系列數字乘法遊戲，且每天她都會玩到膩為止。更精確地說，在第 $i$ 天，Bajtosia 進行了 $n_i$ 場乘法遊戲，其中最後一場遊戲是從 $x = n_i$ 開始的。

對於每一天，給定 $n_i$，請計算對於 $0$ 到 $9$ 的每個數字，有多少場乘法遊戲是以該數字結束的。

輸入格式

第一行包含一個整數 $t$ ($1 \le t \le 1000$)，表示 Bajtosia 進行乘法遊戲的天數。

第二行包含一個由 $t$ 個整數組成的序列 $n_1, n_2, \dots, n_t$ ($1 \le n_i \le 10^{18}$)，表示 Bajtosia 在連續幾天中分別進行了多少場乘法遊戲。

輸出格式

輸出 $t$ 行，每行應包含 $10$ 個整數，分別表示對應的那一天中，以數字 $0, 1, \dots, 9$ 結束的乘法遊戲場數。

範例

範例輸入 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