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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>
using namespace std;
const int MX=51200;
int t,cur_len,a[22],len[MX],fin[MX];
map<long long, vector<vector<int>>> all;
map<long long, vector<long long>> was;
map<long long, int> ans;
vector<int> v,allv[MX];
vector<long long> e,res;
long long n,f[20],comp[MX];
void rec(int l, int cnt, long long cur) {
  if (l>9) {
    if (cnt!=18) {
      long long sv=cur;
      bool was=false;
      while (cur>0) {
        if (cur%10==0) { was=true; break; }
        cur/=10;
      }
      if (!was) all[sv].push_back(v);
    }
    return;
  }
  v[l]=0;
  for (int i=cnt; i>=0; i--) {
    rec(l+1,i,cur);
    cur*=l;
    v[l]++;
  }
}
int main() {
  for (int i=f[0]=1; i<20; i++) f[i]=(f[i-1]*i);
  v.assign(10,0);
  e.assign(10,0);
  rec(1,18,1);
  for (auto it=all.begin(); it!=all.end(); it++) {
    long long cur=it->first,nxt=1;
    while (cur>0) {
      nxt*=(cur%10);
      cur/=10;
    }
    if (it->first==nxt) {
        if (nxt) ans[nxt]=nxt;
    } else {
        auto nxt_it=ans.find(nxt);
        if (nxt_it!=ans.end()) ans[it->first]=nxt_it->second;
    }
  }
  int num=0;
  for (auto it=ans.begin(); it!=ans.end(); it++) {
      auto xt=all.find(it->first);
      for (int idx=0; idx<xt->second.size(); idx++) {
        fin[num]=it->second;
        allv[num]=xt->second[idx];
        for (int i=1; i<10; i++) {
          len[num]+=xt->second[idx][i];
          //printf("%d,",xt->second[idx][i]);
        }
        long long cur=f[len[num]];
        for (int i=1; i<10; i++) if (xt->second[idx][i]) cur/=f[xt->second[idx][i]];
        comp[num]=cur;
        //printf("  %d: %lld = %lld [%d] [len=%d]\n",num,it->first,comp[num],fin[num],len[num]);
        num++;
      }
  }
  //printf("%d\n",num);
  scanf("%d",&t);
  while (t--) {
    scanf("%lld",&n);
    auto wt=was.find(n);
    if (wt==was.end()) {
      long long svn=n;
      for (cur_len=0; n>0; cur_len++, n/=10) a[cur_len]=n%10;
      reverse(a,a+cur_len);
      res=e;
      for (int i=0; i<num; i++) if (len[i]==cur_len) {
        v=allv[i];
        for (int j=0; j<cur_len; j++) {
          int lim=a[j]-1;
          if (j+1==cur_len) ++lim;
          for (int d=0; d<=lim; d++) if (v[d]>0) {
            --v[d];
            long long cur=f[cur_len-j-1];
            for (int idx=1; idx<10; idx++) if (v[idx]) cur/=f[v[idx]];
            res[fin[i]]+=cur;
            ++v[d];
          }
          if (j<cur_len && v[a[j]]>0) --v[a[j]]; else break;
        }
      } else if (len[i]<cur_len) res[fin[i]]+=comp[i];
      assert(res[0]==0);
      res[0]=svn;
      for (int i=1; i<10; i++) res[0]-=res[i];
      was[svn]=res;
    } else res=wt->second;
    printf("%lld",res[0]);
    for (int i=1; i<10; i++) printf(" %lld",res[i]);
    puts("");
  }
  return 0;
}