10
4 108 114
5 30 155
8 193 197
9 71 169
2 163 166
8 120 144
8 22 151
4 21 166
2 46 127
8 38 51
 20
9 142 172
7 132 256
8 245 315
9 496 496
3 345 362
8 13 162
5 342 470
9 16 488
9 467 482
4 471 478
10 92 224
6 228 261
9 54 167
2 402 409
5 9 10
7 225 360
3 438 483
6 252 342
3 491 493
6 296 367
 1
8 1234567890123 123456789012345

0
3
0
1
3
0
5
16
9
1
 0
0
0
0
4
6
13
7
0
0
1
2
3
0
0
2
12
9
1
4
 774752389568

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
long long g[70][12][12];
int xx[1100], a[70];
int p;
long long dp(int n, int s, int f1, int f2) {
  if (n == 0) {
    if (s != 0) return 0;
    if (!f2) return 0;
    return 1;
  }
  if (!f1 && f2) return g[n][xx[s]][p];
  int r = (f1 ? a[n] : p - 1);
  long long res = 0;
  for (int i = 0; i <= r; i++)
    if (i > 0)
      res += dp(n - 1, s ^ (1 << i), f1 && i == r, f2 || i > 0);
    else
      res += dp(n - 1, s ^ f2, f1 && i == r, f2 || i > 0);
  return res;
}
long long calc(long long n, int p) {
  int len = 0;
  while (n) {
    len++;
    a[len] = n % p;
    n /= p;
  }
  return dp(len, 0, 1, 0);
}
int main() {
  for (int i = 2; i <= 10; i++) g[0][0][i] = 1;
  for (int l = 2; l <= 10; l++)
    for (int n = 1; n <= 70; n++)
      for (int k = 0; k <= l; k++)
        g[n][k][l] = g[n - 1][k - 1][l] * k + g[n - 1][k + 1][l] * (l - k);
  for (int i = 1; i < 1024; i++) xx[i] = xx[i >> 1] + (i & 1);
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    long long l, r;
    p = 10, l = 1LL << 58, r = l * 2;
    printf("%lld\n", calc(r, p) - calc(l - 1, p));
  }
  return 0;
}
