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;
long long dp[21][21][21];
int DIGITS[21];
int BASE;
long long solve2(int N, int E, int Q) {
  if (E < 0 || Q < 0) return 0;
  long long& ans = dp[N][E][Q];
  if (ans >= 0) return ans;
  if (N == 0) return ans = (Q == 0 ? 1 : 0);
  ans = 0;
  if (N % 2 != Q % 2) return ans = 0;
  long long place_from_even = 1ll * E * solve2(N - 1, E - 1, Q + 1);
  long long place_from_odd = 1ll * Q * solve2(N - 1, E + 1, Q - 1);
  ans = place_from_odd + place_from_even;
  return ans;
}
long long query(int b, long long r) {
  if (r == 0) return 0;
  BASE = b;
  memset(DIGITS, 0, sizeof(DIGITS));
  for (int i = 0; i < (21); ++i) {
    DIGITS[i] = r % BASE;
    r /= BASE;
  }
  int first = -1;
  for (int d = (21 - 1); d >= (0); --d) {
    if (DIGITS[d] > 0) {
      first = d;
      break;
    }
  }
  long long ans = 0;
  for (int i = 1; i < 21 && i <= first; i += 2) {
    if (i < first) {
      for (int v = (1); v <= (BASE - 1); ++v) {
        ans += solve2(i, BASE - 1, 1);
      }
    } else {
      assert(i == first);
      for (int v = (1); v <= (DIGITS[i] - 1); ++v) {
        ans += solve2(i, BASE - 1, 1);
      }
      for (int smaller = 0; smaller < i; ++smaller) {
        for (int v = (0); v <= (DIGITS[smaller] - 1); ++v) {
          vector<int> parity(BASE, 0);
          for (int z = (smaller + 1); z <= (i); ++z) {
            int dig = DIGITS[z];
            parity[dig] ^= 1;
          }
          parity[v] ^= 1;
          int odds = accumulate(parity.begin(), parity.end(), 0);
          int evens = BASE - odds;
          ans += solve2(smaller, evens, odds);
        }
      }
    }
  }
  vector<int> parity(BASE, 0);
  for (int z = (0); z <= (first); ++z) {
    parity[DIGITS[z]] ^= 1;
  }
  int odds = accumulate(parity.begin(), parity.end(), 0);
  if (odds == 0) ans += 1;
  return ans;
}
int main() {
  memset(dp, -1, sizeof(dp));
  int Q, b;
  long long l, r;
  std::ios::sync_with_stdio(false);
  cin >> Q;
  for (int q = 0; q < (Q); ++q) {
    cin >> b >> l >> r;
    long long ans = query(b, r) - query(b, l - 1);
    cout << ans << endl;
  }
}
