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 long long M = 1e18;
int q, a[65], C[12][12];
bool b[12];
long long f[12][65][12];
inline long long read() {
  long long ans = 0;
  char c = getchar();
  while (c < 48 || c > 57) c = getchar();
  while (c >= 48 && c <= 57)
    ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
  return ans;
}
inline void write(long long x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
inline long long query(int x, long long y) {
  if (!y) return 0;
  long long ans = 0;
  int p = 0, cnt = 0;
  while (y) a[++cnt] = y % x, y /= x;
  for (register int i = 0; i < x; ++i) b[i] = 0;
  for (register int i = 2; i < cnt; i += 2) ans += f[x][i][0] / x * (x - 1);
  if (cnt & 1) return ans;
  for (register int i = cnt; i; --i) {
    for (register int j = 0; j < a[i]; ++j) {
      if (i == cnt && !j) continue;
      if (b[j])
        ans += f[x][i - 1][p - 1] / C[x][p - 1];
      else
        ans += f[x][i - 1][p + 1] / C[x][p + 1];
    }
    b[a[i]] ^= 1;
    if (b[a[i]])
      ++p;
    else
      --p;
  }
  if (!p) ++ans;
  return ans;
}
int main() {
  for (register int i = 2; i <= 10; ++i) {
    f[i][0][0] = 1, f[i][1][1] = i;
    long long t = i;
    for (register int j = 2; t - 1 <= M; ++j, t *= i) {
      for (register int k = 0; k <= i; ++k)
        f[i][j][k] = f[i][j - 1][k + 1] * (k + 1) +
                     (k ? f[i][j - 1][k - 1] * (i - k + 1) : 0);
      if (M / i < t) break;
    }
  }
  for (register int i = 1; i <= 10; ++i) {
    C[i][0] = 1;
    for (register int j = 1; j <= i; ++j) C[i][j] = C[i][j - 1] + C[i - 1][j];
  }
  q = read();
  while (q--) {
    int u = read();
    long long v = read(), w = read();
    write(query(u, w) - query(u, v - 1)), putchar('\n');
  }
  return 0;
}
