1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <unordered_map>
using namespace std;

long next(long a)
{
  long b = 1;
  while (a>0) b *= a%10, a /= 10;
  return b;
}

int last(long a)
{
  while (a>9) a = next(a);
  return a;
}

unordered_map<long, long> C[19][10];

void calc(long r[10], long m, int e, int s = 1)
{
  long a[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  if (e==0)
  {
    a[last(m)]++;
    for (int i = 0; i<10; i++) C[e][i][m] = a[i];
  }
  else if (C[e][0].count(m) > 0)
  {
    for (int i = 0; i<10; i++) a[i] = C[e][i][m];
  }
  else
  {
    for (int i = 0; i<10; i++) calc(a, m*i, e-1);
    for (int i = 0; i<10; i++) C[e][i][m] = a[i];
  }
  for (int i = 0; i<10; i++) r[i] += s*a[i];
}

int main()
{
  int t;
  scanf("%i ", &t);
  while (t--)
  {
    long n, r[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    scanf("%li ", &n);
    for (int i = 0; n>0; n /= 10, i++)
    {
      if (n>=9) calc(r, 1, i+1), calc(r, 0, i, -1);
      while(n>0)
      {
        if (n%10==9) break;
        calc(r, next(n), i);
        n--;
      }
    }
    for (int i = 0; i<10; i++) printf("%li%c", r[i], " \n"[i==9]);
  }
  return 0;
}