#include <bits/stdc++.h>

using namespace std;

//#define _DEBUG
//#ifdef _DEBUG
//template<typename T1, typename T2> auto& operator<<(ostream& o, pair<T1, T2> a) { return o << "(" << a.first << ", " << a.second << ")"; }
//template<typename T, typename OS> auto& operator<<(OS& o, T a) { o << "{"; for(auto b : a) o << b << ", "; return o << "}"; }
//#define dbg(x...) cerr << "[" #x "]: ", [](auto... args) { ((cerr << args << ", "),...) << "\n"; }(x)
//#else
//#define dbg(...)
//#endif

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
using vi = vector<int>;

ll f(ll v) {
  if(v < 10) {
    return v;
  }

  ll next = 1;
  while(v) {
    next *= v % 10;
    v /= 10;
  }

  return next;
}

ll getv(ll v) {
  if(v < 10) {
    return v;
  }
  return getv(f(v));
}

/*
- zera sa bardzo czesto - jezeli liczba ma jakies zero -> 0, jezeli ma 2 i 5 -> 0 (bo bedzie miala 0 w nastepnym)
- jedynki - bezposrednio tylko z: 1, 11, 111, 1111, 11111, 111111, zeby takie cos powstalo to musialoby istniec takie 11..1, ze dzielniki byly by tylko 1..9
- moze cos waznego, rozklad liczby kazdej bedzie taki: 2,3,5,7 wiec moze latwo relatywnie przeiterowac po wszystkich??!?!?


okej idea jest taka:ADJ_OFFSET_SINGLESHOT

przechodzimy przez wszystkie liczby v majace w rozkladzie tylko 2, 3, 5, 7 bedace <= n

v -> z

occ[z] += z-ilu-liczb-da-sie-dojsc-do-z + 1 ()

jezeli z v da sie dojsc do jakies innej liczby wczesniej juz sprawdzanej, to nie dodajemy tego jeden

w ten sposob sprawdzamy dla wszystkich liczb 1..9 zero to jest po prostu n - sum(1..9)

jaka zlozonosc?
mamy tylko 193 takie liczby, wiec zlozonosc to bedzie  t * 193 * zlozonosc_znajdowania_do_ilu_da_sie_dojsc + 60000 * zlozonosc_funkcji_rekurencyjnej (to eksperymentalnie wiadomo, ze spoko)
czyli wychodzi jakies 200 000 * zlozonosc_znajdowania_do_ilu_da_sie_dojsc
lub jezeli udalo by sie zmapowac liczby do ktorych da sie dojsc (pewnie nie), to 200 * zlozonosc_dodania_tych_wszystkich_liczb(czyli ich liczba prawdopodobnie)


*/

ll factorial(ll n) {
  if(n == 0) {
    return 1;
  }
  return factorial(n - 1) * n;
}

ll countAny(ll n, vector<ll>& cs, ll sum, const vector<ll>& fact) {
  ll ans = fact[sum];
  return ans;
}

ll countGreater(ll n, vector<ll> cs, const vector<ll>& fact, const vector<int>& ndigits) {


  ll ans = 0;

  //ll sum = accumulate(cs.begin(), cs.end(), 0);
  ll sum = ndigits.size();  

  ll denom = 1;
  for(auto c : cs) {
    denom *= fact[c];
  }

  for(int i = 0; i < ndigits.size(); i++) {
    for(int j = ndigits[i] + 1; j < cs.size(); j++) {
      if(cs[j] > 0) {
        denom /= cs[j];
        cs[j]--;        
        ans += fact[sum - 1] / denom;;
        
        cs[j]++;
        denom *= cs[j];
      }
    }
    if(cs[ndigits[i]] == 0) {
      break;
    }
    denom /= cs[ndigits[i]];
    cs[ndigits[i]]--;
    sum--;
  }
  return ans;
}

static ll iters = 0;

ll countPossibleSources(ll tc, ll thc, ll fc, ll sc, ll n, const vector<ll>& fact, ll v, const vector<int>& n_dec) {
  ll ndigits = n_dec.size();
  ll ans = 0;
  for(ll fours = 0; fours * 2 <= tc; fours++) {
    for(ll eights = 0; eights * 3 + fours * 2 <= tc; eights++) {
      for(ll nines = 0; nines * 2 <= thc; nines++) {
        for(ll sixes = 0; sixes + 2 * fours + 3 * eights <= tc && sixes + 2 * nines <= thc; sixes++) {
          for(ll ones = 0; ones <= ndigits; ones++) {
            iters++;
            ll twos = tc - fours * 2 - eights * 3 - sixes;
            ll threes = thc - nines * 2 - sixes;
            ll digits = twos + threes + fours + eights + nines + sixes + fc + sc + ones;
            if(digits > ndigits || digits == 0) {
              continue;
            }
            if(digits <= ndigits) {
              ans += fact[digits] / (fact[twos] * fact[threes] * fact[fours] * fact[fc] * fact[sixes] * fact[sc] * fact[eights] * fact[nines] * fact[ones]);
            }
            if(digits == ndigits) {
              ans -= countGreater(n, {0, ones, twos, threes, fours, fc, sixes, sc, eights, nines}, fact, n_dec);
            }
          }
        }
      }
    }
  }

  // ll b = 0;
  // for(int i = 1; i <= n; i++) {
  //   if(f(i) == v) {
  //     b++;
  //   }
  // }
  // assert(b == ans);
  return ans;
}

vector<tuple<ll, ll, ll, ll, ll, ll>> getVs(ll n) {
  vector<tuple<ll, ll, ll, ll, ll, ll>> vs;
  ll two = 1;
  ll tc = 0;
  while(two <= n) {
    ll three = 1;
    ll thc = 0;
    while(two * three <= n) {
      ll five = 1;
      ll fc = 0;
      while(two * three * five <= n) {
        ll seven = 1;
        ll sc = 0;
        while(two * three * five * seven <= n) {
          ll v = getv(two * three * five * seven);
          if(v) {
            vs.push_back({v, tc, thc, fc, sc, two * three * five * seven});
          }
          seven *= 7;
          sc++;
        }
        five *= 5;
        fc++;
      }
      three *= 3;
      thc++;
    }
    two *= 2;
    tc++;
  }
  sort(all(vs));
  return vs;
}

vector<ll> solvet(ll n, const vector<tuple<ll, ll, ll, ll, ll, ll>>& pvs, const vector<ll>& fact) {  
  vector<int> digits;
  ll tmp = n;
  while(tmp) {
    digits.push_back(tmp % 10);
    tmp /= 10;
  }
  reverse(digits.begin(), digits.end());


  vector<ll> ans(10);
  set<ll> vs;

  for(auto [v, tc, thc, fc, sc, prod] : pvs) {
    if(v > n) {
      break;
    }
    vs.insert(v);
    ans[v] += countPossibleSources(tc, thc, fc, sc, n, fact, prod, digits);
  }  

  for(auto v : vs) {
    if(vs.count(f(v)) && v > 9) {
      ans[f(v)]--;
    }
  }

  ans[0] = n - std::accumulate(ans.begin(), ans.end(), 0ll);
  return ans;
}

void solve2(const vector<ll>& ns) {
  vector<ll> fact(20);
  fact[0] = 1;
  for(int i = 1; i < fact.size(); i++) {
    fact[i] = i * fact[i - 1];
  }

  ll maxn = 0;
  for(auto n : ns) {
    maxn = max(maxn, n);
  }

  auto pvs = getVs(maxn);
  for(auto n : ns) {
    auto ans = solvet(n, pvs, fact);
    for(auto v : ans) {
      cout << v << " ";
    }
    cout << "\n";
  }
}

vector<ll> solve(ll n) {
  vector<ll> fact(20);
  fact[0] = 1;
  for(int i = 1; i < fact.size(); i++) {
    fact[i] = i * fact[i - 1];
  }

  vector<int> digits;
  ll tmp = n;
  while(tmp) {
    digits.push_back(tmp % 10);
    tmp /= 10;
  }
  reverse(digits.begin(), digits.end());


  vector<ll> ans(10);

  set<ll> vs;

  ll two = 1;
  ll tc = 0;
  while(two <= n) {
    ll three = 1;
    ll thc = 0;
    while(two * three <= n) {
      ll five = 1;
      ll fc = 0;
      while(two * three * five <= n) {
        ll seven = 1;
        ll sc = 0;
        while(two * three * five * seven <= n) {
          ll v = getv(two * three * five * seven);
          if(v) {
            //ans[v] += countPossibleSources(tc, thc, fc, sc, n, fact, two * three * five * seven, digits);
            vs.insert(v);
          }
          seven *= 7;
          sc++;
        }
        five *= 5;
        fc++;
      }
      three *= 3;
      thc++;
    }
    two *= 2;
    tc++;
  }

  for(auto v : vs) {
    if(vs.count(f(v)) && v > 9) {
      ans[f(v)]--;
    }
  }

  ans[0] = n - std::accumulate(ans.begin(), ans.end(), 0ll);
  return ans;
}

vector<ll> brute(ll n) {
  vector<ll> ans(10);
  for(ll i = 1; i <= n; i++) {
    ans[getv(i)]++;
  }
  return ans;
}

void solve() {
  ll n;
  cin >> n;
  auto vs = solve(n);
  for(auto v : vs) {
    cout << v << "\n";
  }
  /*
  auto t1 = chrono::high_resolution_clock::now();
  for(int i = 0; i < 1; i++) {
    auto vs = solve(n);
    for(auto v : vs) {
      cout << v << "\n";
    }
  }
  auto t2 = chrono::high_resolution_clock::now();
  cout << "\n\n" << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count();
  //return;56
  cout << "\n--------------\n";
  auto vs = brute(n);
  for(auto v : vs) {
    cout << v << "\n";
  }
    */
}

void solveqq() {
  ll maxv = 1000000000000000000;

  /*
  set<ll> vs1;
  {
    ll count = 0;
    for(int i = 0; i < maxv; i++) {
      if(getv(i) != 0) {
        count++;
        vs1.insert(i);
      }
    }
    cout << count << "\n";
  }
    */




  ll count = 0;
  ll count2 = 0;

  ll two = 1;
  ll tc = 0;


  while(two < maxv) {
    ll three = 1;
    ll thc = 0;
    while(two * three < maxv) {
      ll five = 1;
      ll fc = 0;
      while(two * three * five < maxv) {
        ll seven = 1;
        ll sc = 0;
        while(two * three * five * seven < maxv) {
          //cout << two * three * five * seven << "\n";
          count2++;
          if(getv(two * three * five * seven)) {
            cout << getv(two * three * five * seven) << "\n";
            count++;
            //count2 += factorial(tc + thc + fc + sc) / (factorial(tc) * factorial(thc) * factorial(fc) * factorial(sc));
            //count2++;
          }
          seven *= 7;
          sc++;
        }
        five *= 5;
        fc++;
      }
      three *= 3;
      thc++;
    }
    two *= 2;
    tc++;
  }
  cout << "\n-----------------------\n" << count;
  cout << "\n-----------------------\n" << count2;
}

int main() {
  //#define ASDASDDSA

  #ifdef ASDASDDSA
  
  //solve(1000000000000000000);
  int64_t maxTime = 0;
  for(int64_t n = 10; n <= 1000000000000000000; n *= 10) {
    for(int i = 0; i < 20; i++) {            
      auto t1 = chrono::high_resolution_clock::now();
      solve2(vector<ll>(1000, min(1000000000000000000, n + i * 18)));
      auto t2 = chrono::high_resolution_clock::now();
      maxTime = max(maxTime, chrono::duration_cast<chrono::milliseconds>(t2 - t1).count());
    }
  }  

  cout << maxTime;

  auto t1 = chrono::high_resolution_clock::now();
  solve2(vector<ll>(1000, 1000000000000000000));
  auto t2 = chrono::high_resolution_clock::now();
  auto time = chrono::duration_cast<chrono::milliseconds>(t2 - t1).count();
  cout << "\n" << time;

  // for(int i = 0; i < 1000; i++) {
  //   auto vs = solve(1000000000000000000);
  //   for(auto v : vs) {
  //     //cout << v << "\n";
  //   }
  // }
  //cout << iters;
    
  #endif
  // for(int i = 1; i < 1000000; i++) {
  //   auto s = solve(i);
  //   auto b = brute(i);
  //   if(solve(i) != brute(i)) {
  //     assert(false);
  //   }
  // }
  // return 0;

  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  cin >> t;
  //t = 10;
  vector<ll> ns(t);  
  int i = 0;
  for(auto& n : ns) {
      cin >> n;
      i++;
  }
  solve2(ns);

  //while(t--) {
  //  solve();
  //  cout << "\n";
  //}
  return 0;
}