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 开始进行乘法游戏，并且总是从连续的数值开始： 第一次游戏从 $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