背景

PA 2025 R3B.

题目描述

对于非负整数 $n$，定义函数 $f(n)$：

• 令 $n$ 的十进制表示为 $\overline{a_1a_2\ldots a_k}$。
• 则 $f(n)=a_1a_2\cdots a_k$。

换言之，$f(n)$ 就是将 $n$ 十进制表示下的数位相乘得到的结果。

对于非负整数 $x$，按如下程序执行操作：

1. 若 $x\le 9$，终止操作；
2. 否则令 $x\gets f(x)$，回到 1。

举例

1. $57\to 5\times 7=35\to 3\times 5=15\to 1\times 5=5$。
2. $255\to 2\times 5\times 5=50\to 5\times 0=0$。

可以证明，对于任意非负整数 $x$，这个操作都一定会终止。

$T$ 组数据，每组数据给定 $n$，对于 $i=0,1,\ldots,9$，求出：

• 有多少个 $1\le j\le n$ 满足将 $j$ 操作后最终会得到 $i$。

输入格式

本题单个测试点内含有多组测试数据。

第一行，一个正整数 $T$。

第二行，$T$ 个正整数 $n$，描述 $T$ 组数据。

输出格式

输出 $T$ 行，每行 $10$ 个非负整数，每行第 $i$ 个整数表示：

• 有多少个 $1\le j\le n$ 满足将 $j$ 操作后最终会得到 $i-1$。

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

提示

• $1\le T\le 10^3$；
• $1\le n\le 10^{18}$。