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 comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int maxn = 4e3 + 10;
const int maxx = 4e5 + 10;
const double EPS = 1e-8;
const double eps = 1e-8;
const int mod = 1e9 + 7;
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline bool scan_d(T &ret) {
  char c;
  int sgn;
  if (c = getchar(), c == EOF) {
    return 0;
  }
  while (c != '-' && (c < '0' || c > '9')) {
    c = getchar();
  }
  sgn = (c == '-') ? -1 : 1;
  ret = (c == '-') ? 0 : (c - '0');
  while (c = getchar(), c >= '0' && c <= '9') {
    ret = ret * 10 + (c - '0');
  }
  ret *= sgn;
  return 1;
}
inline bool scan_lf(double &num) {
  char in;
  double Dec = 0.1;
  bool IsN = false, IsD = false;
  in = getchar();
  if (in == EOF) return false;
  while (in != '-' && in != '.' && (in < '0' || in > '9')) in = getchar();
  if (in == '-') {
    IsN = true;
    num = 0;
  } else if (in == '.') {
    IsD = true;
    num = 0;
  } else
    num = in - '0';
  if (!IsD) {
    while (in = getchar(), in >= '0' && in <= '9') {
      num *= 10;
      num += in - '0';
    }
  }
  if (in != '.') {
    if (IsN) num = -num;
    return true;
  } else {
    while (in = getchar(), in >= '0' && in <= '9') {
      num += Dec * (in - '0');
      Dec *= 0.1;
    }
  }
  if (IsN) num = -num;
  return true;
}
void Out(long long a) {
  if (a < 0) {
    putchar('-');
    a = -a;
  }
  if (a >= 10) Out(a / 10);
  putchar(a % 10 + '0');
}
void print(long long a) { Out(a), puts(""); }
int q, b;
int a[70];
int dp[70][2][2][2][2][2][2][2][2][2][2][2];
bool check(int *t) {
  for (int i = 0; i <= 9; i++) {
    if (t[i]) return 0;
  }
  return 1;
}
long long dfs(int pos, int qd, int sta, bool limit, int *c) {
  if (pos == -1) return sta == 1;
  if (!limit && qd == 0 &&
      dp[pos][sta][c[0]][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]][c[7]][c[8]]
        [c[9]] != -1)
    return dp[pos][sta][c[0]][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]][c[7]][c[8]]
             [c[9]];
  int up = limit ? a[pos] : (b - 1);
  long long tmp = 0;
  for (int i = 0; i <= up; i++) {
    if (i == 0 && qd == 1)
      tmp += dfs(pos - 1, 1, sta, limit && i == a[pos], c);
    else {
      c[i] ^= 1;
      int st;
      if (check(c))
        st = 1;
      else
        st = 0;
      tmp += dfs(pos - 1, 0, st, limit && i == a[pos], c);
      c[i] ^= 1;
    }
  }
  if (!limit && qd == 0)
    dp[pos][sta][c[0]][c[1]][c[2]][c[3]][c[4]][c[5]][c[6]][c[7]][c[8]][c[9]] =
        tmp;
  return tmp;
}
long long solve(long long x) {
  int pos = 0;
  int t[12];
  memset(t, 0, sizeof(t));
  ;
  while (x) {
    a[pos++] = x % b;
    x /= b;
  }
  return dfs(pos - 1, 1, 0, true, t);
}
int main() {
  scan_d(q);
  memset(dp, -1, sizeof(dp));
  ;
  while (q--) {
    long long l, r;
    scan_d(b), scan_d(l), scan_d(r);
    print(solve(r) - solve(l - 1));
  }
}
