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;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T bpow(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
int toInt(string s) {
  int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int toLlint(string s) {
  long long int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int ts, kk = 1;
int m, n;
int a[22], b[22];
long long int p[2][2][2][9][65][(1 << 10)];
int vs[2][2][2][9][65][(1 << 10)];
long long int dp(bool st, bool bg, bool sm, int i, int x) {
  if (i == 65) {
    if (x == 0) return 1;
    return 0;
  }
  long long int &pr = p[st][bg][sm][m - 2][i][x];
  if (vs[st][bg][sm][m - 2][i][x] == kk) return pr;
  if (vs[st][bg][sm][m - 2][i][x] && st && bg && sm) return pr;
  vs[st][bg][sm][m - 2][i][x] = kk;
  pr = 0;
  int mn = (bg == 1) ? 0 : a[i];
  int mx = (sm == 1) ? (m - 1) : b[i];
  for (int k = mn; k <= mx; k++) {
    bool nst = (st == 1) ? 1 : (k > 0);
    bool nbg = (bg == 1) ? 1 : (k > mn);
    bool nsm = (sm == 1) ? 1 : (k < mx);
    int nx = x;
    if (nst) {
      nx ^= (1 << k);
    }
    pr += dp(nst, nbg, nsm, i + 1, nx);
  }
  return pr;
}
int main() {
  int t, i, j, k;
  scanf("%d", &ts);
  while (ts--) {
    kk++;
    long long int x, y;
    scanf("%d%lld%lld", &m, &x, &y);
    for (i = 64; x || y; i--) {
      a[i] = x % m;
      b[i] = y % m;
      x /= m;
      y /= m;
    }
    printf("%lld\n", dp(0, 0, 0, i + 1, 0));
  }
  return 0;
}
