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>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
int fx[4] = {0, 1, 0, -1};
int fy[4] = {1, 0, -1, 0};
const long long M = 2e5 + 10, M2 = 1e6 + 10, oo = 1e18 + 7, mod = 998244353;
const long long MC = (1 << 22) + 5;
long long dp[12][62][1030], sm[12][62][1030];
int getln(int base) {
  int ret = 0;
  long long mx = oo;
  while (mx) {
    ret++;
    mx /= base;
  }
  return ret;
}
string tostr(long long x, int b) {
  string s = "";
  while (x) {
    s += (char)((x % b) + '0');
    x /= b;
  }
  return s;
}
void precomp() {
  for (int base = 2; base <= 10; base++) {
    int maxln = getln(base);
    dp[base][0][0] = 1;
    for (int ln = 1; ln <= maxln; ln++) {
      for (int mask = 0; mask < (1LL << base); mask++) {
        for (int d = 1; d < base; d++) {
          for (int pre = 0; pre < ln; pre++) {
            int zeros = ln - 1 - pre;
            int premask = (mask ^ (1 << d));
            premask ^= (zeros & 1);
            dp[base][ln][mask] += dp[base][pre][premask];
          }
        }
      }
    }
    sm[base][0][0] = 1;
    for (int ln = 1; ln <= maxln; ln++) {
      for (int mask = 0; mask < (1LL << base); mask++) {
        for (int zrs = 0; zrs <= ln; zrs++) {
          int nmask = (mask ^ (zrs & 1));
          sm[base][ln][nmask] += dp[base][ln - zrs][mask];
        }
      }
    }
  }
}
long long magic(string s, int b) {
  long long ret = 0;
  int ln = s.length();
  int premask = 0;
  for (int lopos = 0; lopos < ln; lopos++) {
    int curd = s[lopos] - '0', rest = ln - lopos - 1;
    for (int d = 0; d < curd; d++) {
      if (lopos == 0 && d == 0) continue;
      int curmask = (premask ^ (1LL << d));
      ret += sm[b][rest][curmask];
    }
    premask = (premask ^ (1LL << curd));
  }
  for (int i = 1; i < ln; i++) {
    ret += dp[b][i][0];
  }
  if (premask == 0) ret++;
  return ret;
}
void solve() {
  int q;
  cin >> q;
  while (q--) {
    long long lb, rb, b;
    cin >> b >> lb >> rb;
    string l = tostr(lb - 1, b), r = tostr(rb, b);
    if (l == "") l = "0";
    cout << magic(r, b) - magic(l, b) << '\n';
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  precomp();
  solve();
  return 0;
}
