Multiplicative Digit Convergence

For a nonnegative integer \(n\), define a function \(f(n)\) as follows:

• Express \(n\) in its decimal representation as \(\overline{a_1a_2\ldots a_k}\).
• Then \(f(n)=a_1\times a_2\times\cdots\times a_k\).

In other words, \(f(n)\) is the product of the decimal digits of \(n\). Notice that if \(n\le 9\) then \(f(n)=n\).

For a nonnegative integer \(x\), perform the following iterative process:

1. If \(x\le 9\), stop the process.
2. Otherwise, assign \(x \gets f(x)\) and repeat from step 1.

It can be proved that for any nonnegative integer \(x\) this process terminates, ending with a single digit.

Example

• \(57 \to 5\times7=35 \to 3\times5=15 \to 1\times5=5\).
• \(255 \to 2\times5\times5=50 \to 5\times0=0\).

There are \(T\) test cases. For each test case, you are given a positive integer \(n\). For each digit \(i=0,1,\ldots,9\), count how many integers \(j\) (with \(1\le j\le n\)) eventually become \(i\) when this process is applied.

inputFormat

The first line contains the number of test cases, \(T\) (\(T \ge 1\)). Each of the next \(T\) lines contains a positive integer \(n\).

outputFormat

For each test case, output a single line containing 10 space‐separated integers. The \(i\)th integer (0-indexed) is the number of \(j\) with \(1\le j\le n\) that eventually converge to the digit \(i\) after applying the process.

sample

1
10

1 1 1 1 1 1 1 1 1 1