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 maxn = 2000 + 10;
long long f[20][70][maxn], l, r, g[20][70][maxn], sum[20][70][maxn];
int q, k, tot, d[100], tmp[100];
void dp(int x) {
  f[x][0][0] = 1;
  for (int i = 0; i < 60; i++) {
    for (int j = 0; j < (1 << x); j++)
      if (f[x][i][j])
        for (int k = 0; k < x; k++) {
          int nj = j ^ (1 << k);
          f[x][i + 1][nj] += f[x][i][j];
        }
  }
  for (int i = 0; i <= 60; i++)
    for (int j = 0; j < (1 << x); j++)
      for (int k = 1; k < x; k++) g[x][i + 1][j ^ (1 << k)] += f[x][i][j];
  for (int j = 0; j < (1 << x); j++) {
    sum[x][0][j] = g[x][0][j];
    for (int i = 1; i <= 60; i++) sum[x][i][j] = sum[x][i - 1][j] + g[x][i][j];
  }
}
void split(long long x) {
  tot = 0;
  while (x) {
    tmp[++tot] = x % k;
    x /= k;
  }
  for (int i = 1; i <= tot; i++) d[i] = tmp[tot + 1 - i];
}
long long dfs(int be, int s, int p, int sta) {
  if (s == 1) {
    if (be)
      return f[k][tot - p + 1][sta];
    else
      return sum[k][tot - p + 1][sta];
  }
  if (p == tot + 1) return sta == 0;
  long long res = 0;
  for (int i = 0; i < d[p]; i++)
    if (be || i)
      res += dfs(1, 1, p + 1, sta ^ (1 << i));
    else
      res += dfs(0, 1, p + 1, 0);
  res += dfs(1, 0, p + 1, sta ^ (1 << d[p]));
  return res;
}
long long calc(long long x) {
  if (!x) return 0;
  split(x);
  return dfs(0, 0, 1, 0);
}
int main() {
  for (int i = 2; i < 10; i++) dp(i);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%lld%lld", &k, &l, &r);
    printf("%lld\n", calc(r) - calc(l - 1));
  }
}
