#include <bits/stdc++.h>
using namespace std;
int GLL(long long& x) { return scanf("%lld", &x); }
int GI(int& x) { return scanf("%d", &x); }
int mask(int x) { return 1 << x; }
bool contains(int s, int x) { return s & mask(x); }
const int MAXB = 11;
const int MAXD = 66;
const int MAXM = 1024 + 5;
long long cnt[MAXB][MAXD][MAXM];
int q, b;
long long l, r;
vector<int> rep;
long long solve(long long x) {
  if (x == 0) return 0;
  rep.clear();
  while (x) {
    rep.push_back(x % b);
    x /= b;
  }
  reverse(rep.begin(), rep.end());
  long long res = 0;
  for (int lz = 1; lz < rep.size(); lz++) {
    for (int d = 1; d <= (int)(b - 1); d++) {
      res += cnt[b][rep.size() - lz - 1][mask(d)];
    }
  }
  int prefix = 0;
  for (int match = 0; match < (int)(rep.size()); match++) {
    for (int d = (match == 0); d < rep[match]; d++) {
      int m = prefix ^ mask(d);
      res += cnt[b][rep.size() - match - 1][m];
    }
    prefix ^= mask(rep[match]);
  }
  if (prefix == 0) res++;
  return res;
}
long long check(long long x) {
  long long res = 0;
  for (int t = 1; t <= (int)(x); t++) {
    int m = 0;
    long long y = t;
    while (y) {
      m ^= mask(y % b);
      y /= b;
    }
    if (m == 0) res++;
  }
  return res;
}
int main() {
  memset(cnt, 0, sizeof cnt);
  for (b = 2; b <= 10; b++) {
    cnt[b][0][0] = 1;
    for (int d = 0; d < (int)(MAXD - 1); d++) {
      for (int m = 0; m < (int)(mask(b)); m++) {
        if (cnt[b][d][m]) {
          for (int x = 0; x < (int)(b); x++) {
            cnt[b][d + 1][m ^ mask(x)] += cnt[b][d][m];
          }
        }
      }
    }
  }
  GI(q);
  while (q--) {
    GI(b);
    GLL(l);
    GLL(r);
    printf("%lld\n", solve(r) - solve(l - 1));
  }
  return 0;
}
