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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <array>
#include <iostream>
#include <vector>

#define MAX_N 5000

class DigitsSet {
public:
  std::array<int, 10> arr;

  void print() {
    for(int i = 0; i < 10; i++) {
      std::cout << arr[i];
      if(i != 9) {
        std::cout << " ";
      }
    }
  }
};

class SolutionMapping {
public:
  int sourceIndex{};
  long long n{};
  DigitsSet result{};

  SolutionMapping(int sourceIndex, long long n): sourceIndex(sourceIndex), n(n) {

  }
};


class MnoSolver {
  std::vector<uint8_t> digitsCache;
  std::vector<long long> nVector;
  std::vector<SolutionMapping> solutions;
  long long biggestN = 0;

public:
  MnoSolver() {
    digitsCache.reserve(1500000000);
    digitsCache.emplace_back(0);
    int t;
    std::cin >> t;
    nVector.reserve(t);
    for(int i = 0; i < t; i++) {
      long long n;
      std::cin >> n;
      biggestN = std::max(n, biggestN);
      solutions.emplace_back(i, n);
    }
  }

  void solve() {
    sortSolutionsByN();
    fillCacheUpToMax();
    sortSolutionsByIndex();

    for(auto & solution : solutions) {
      solution.result.print();
      std::cout << "\n";
    }
  }

private:
  void fillCacheUpToMax() {
    DigitsSet currentSet{};
    int nextSolutionIndex = 0;

    for(int i = 1; i < 10; i++) {
      digitsCache.emplace_back(i);
      currentSet.arr[digitsCache[i]]++;
      if(solutions[nextSolutionIndex].n == i) {
        solutions[nextSolutionIndex].result = currentSet;
        nextSolutionIndex++;
      }
    }

    for(int i = 10; i <= biggestN; i++) {
      digitsCache.emplace_back(getDigitFrom(i));
      currentSet.arr[digitsCache[i]]++;
      if(solutions[nextSolutionIndex].n == i) {
        solutions[nextSolutionIndex].result = currentSet;
        nextSolutionIndex++;
      }
    }
  }

  void sortSolutionsByN() {
    std::qsort(solutions.data(), solutions.size(), sizeof(decltype(solutions)::value_type),
     [](const void* x, const void* y)
     {
       const auto* arg1 = static_cast<const SolutionMapping*>(x);
       const auto* arg2 = static_cast<const SolutionMapping*>(y);
       const auto cmp = arg1->n - arg2->n;
       if (cmp < 0)
         return -1;
       if (cmp > 0)
         return 1;
       return 0;
     });
  }

  void sortSolutionsByIndex() {
    std::qsort(solutions.data(), solutions.size(), sizeof(decltype(solutions)::value_type),
     [](const void* x, const void* y)
     {
       const auto* arg1 = static_cast<const SolutionMapping*>(x);
       const auto* arg2 = static_cast<const SolutionMapping*>(y);
       const auto cmp = arg1->sourceIndex - arg2->sourceIndex;
       if (cmp < 0)
         return -1;
       if (cmp > 0)
         return 1;
       return 0;
     });
  }

  uint8_t getDigitFrom(int n) const {
    int nextN = 1;
    while(n > 0) {
      nextN *= n % 10;
      n /= 10;
    }
    return digitsCache[nextN];
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  MnoSolver solver;
  solver.solve();

  return 0;
}