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

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        final int N = 100;
        long[][] C = new long[N][N];
        boolean[][][][] was = new boolean[2][11][66][1 << 10];
        long[][][][] dp = new long[2][11][66][1 << 10];

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            C[0][0] = 1;
            for (int i = 1; i < N; i++) {
                C[i][0] = 1;
                for (int j = 1; j < N; j++) {
                    C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
                }
            }

            boolean stress = false;
            if (stress) {
                Random random = new Random(0);
                for (int i = 0; i < (int) 1e5; i++) {
                    int b = random.nextInt(9) + 2;
                    long r = (long) 1e18 - random.nextInt(1000000);
                    long l = (long) 1e18 - random.nextInt(1000000);
                    solve(b, l);
                    solve(b, r);
                    if (i < (int) 1e3) {
                        b = 10;
                        r = random.nextInt((int) 1e4);
                        long u = solve(b, r);
                        long v = dummy(b, r);
                        if (u != v) {
                            throw new AssertionError(b + " " + r + " " + u + " " + v);
                        }
                    }
                }
            }

            int numQueries = in.nextInt();
            for (int queryId = 0; queryId < numQueries; queryId++) {
                int b = in.nextInt();
                long l = in.nextLong();
                long r = in.nextLong();
                out.println(solve(b, r) - solve(b, l - 1));
            }
        }

        private long solve(int b, long r) {
            if (r == 0) {
                return 1;
            }
            int[] digits = getDigits(b, r);
            int n = digits.length;

            long res = 1;
            for (int numberLen = 1; numberLen < n; numberLen++) {
                res += calc(b, numberLen, 0, 0);
            }

            // number len equals n
            for (int prefLen = 0; prefLen <= n; prefLen++) {
                int mask = 0;
                for (int i = 0; i < prefLen; i++) {
                    mask ^= 1 << digits[n - i - 1];
                }
                if (prefLen == n) {
                    res += calc(b, 0, mask, 1);
                    continue;
                }
                for (int last = 0; last < digits[n - prefLen - 1]; last++) {
                    if (last == 0 && prefLen == 0) {
                        continue;
                    }
                    mask ^= 1 << last;
                    res += calc(b, n - prefLen - 1, mask, 1);
                    mask ^= 1 << last;
                }
            }
            return res;
        }

        private long calc(int base, int n, int mask, int leadingZeroAllowed) {
            if (n == 0) {
                return mask == 0 ? 1 : 0;
            }
            if (was[leadingZeroAllowed][base][n][mask]) {
                return dp[leadingZeroAllowed][base][n][mask];
            }
            was[leadingZeroAllowed][base][n][mask] = true;
            long[] d = new long[n + 1];
            long[] nd = new long[n + 1];
            d[0] = 1;
            for (int digit = 0; digit < base; digit++) {
                Arrays.fill(nd, 0);
                for (int old = 0; old <= n; old++) {
                    if (d[old] == 0) {
                        continue;
                    }
                    for (int here = 0; here + old <= n; here++) {
                        if (here % 2 != ((mask >> digit) & 1)) {
                            continue;
                        }
                        long ways = C[n - old][here];
                        if (leadingZeroAllowed == 0 && digit == 0) {
                            ways = C[n - 1][here];
                        }
                        nd[old + here] += d[old] * ways;
                    }
                }
                long[] t = d;
                d = nd;
                nd = t;
            }
            dp[leadingZeroAllowed][base][n][mask] = d[n];
            return d[n];
        }

        private int[] getDigits(int b, long r) {
            int n = 0;
            long x = r;
            while (x > 0) {
                x /= b;
                ++n;
            }
            int[] digits = new int[n];
            n = 0;
            x = r;
            while (x > 0) {
                digits[n] = (int) (x % b);
                x /= b;
                ++n;
            }
            return digits;
        }

        private long dummy(int b, long r) {
            int res = 1; // zero
            for (int i = 1; i <= r; i++) {
                int[] d = getDigits(b, i);
                int mask = 0;
                for (int j = 0; j < d.length; j++) {
                    mask ^= 1 << d[j];
                }
                if (mask == 0) {
                    ++res;
                }
            }
            return res;
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

