题目描述

Bajtosia 最近学会了乘法，觉得特别有趣。她发明了一个数字乘法的游戏：先在黑板上写下一个正整数 $x$，然后把这个数的各个十进制数字相乘，用结果替换原来的 $x$。她不断重复这个步骤，直到 $x$ 变成一位数为止，游戏就以这个数字结束。可以证明，无论从哪个 $x$ 开始，游戏总会结束。

例如，游戏从 $x=57$ 开始。第一步，Bajtosia 算出 $5 \cdot 7 = 35$。第二步，她算出 $3 \cdot 5 = 15$。最后一步，算出 $1 \cdot 5 = 5$。因为 $5$ 是一位数，游戏就停在 $5$ 上。

如果从 $x=255$ 开始，第一步她得到 $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$ 天里，字节西亚每天放学后都玩这个游戏，直到玩腻为止。具体来说，第 $i$ 天她玩了 $n_{i}$ 次，最后一次从 $x=n_{i}$ 开始。

请你根据每天的 $n_{i}$，算出 $0$ 到 $9$ 每个数字作为游戏结束结果的次数。

输入格式

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 1000)$，表示 Bajtosia 玩乘法游戏的天数。

第二行包含 $t$ 个整数 $n_{1}, n_{2}, \ldots, n_{t}$ $(1 \leq n_{i} \leq 10^{18})$，表示每天她玩了多少次乘法游戏。

输出格式

输出 $t$ 行，每行包含 $10$ 个整数，依次表示当天游戏结束在 $0,1,\ldots ,9$ 的次数。

5
10 56 57 123 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