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>
#define int long long

using namespace std;

const int MaxK = 100;
const int MaxN = 1e5 + 15;

bool used[MaxK][MaxK];
long long cnk[MaxK][MaxK];

int cnt[MaxK];
long long dp[MaxK][MaxK];
long long dp2[25][25][2048];
long long ans[MaxN];

long long getCnk(int n, int k)
{
    if(!used[n][k])
    {
        used[n][k] = true;
        if(k == n || k == 0)
            cnk[n][k] = 1;
        else
        if(k < n)
            cnk[n][k] = getCnk(n - 1, k - 1) + getCnk(n - 1, k);
    }
    return cnk[n][k];
}

bool good(string & s, int b)
{
    for(int i = 0; i < b; ++i)
        cnt[i] = 0;
    for(int i = 0; i < s.size(); ++i)
        ++cnt[s[i] - '0'];
    for(int i = 0; i < b; ++i)
        if(cnt[i] & 1)
            return false;
    return true;
}

long long anotherGet(int a, int b, int pos, int LEN)
{
    long long res = 0;
    for(int k = 0; k < a; ++k)
        if(k || pos)
        {
            ++cnt[k];
            long long cur = 1;

            int all = 0;
            int len = LEN;
            int mask = 0;

            for(int i = 0; i < b; ++i)
                if(cnt[i] & 1)
                {
                    ++all;
                    mask |= (1 << i);
                }

            if(all > LEN)
                continue;

            cur = dp2[0][len][mask];

            --cnt[k];
            res += cur;
        }
    return res;
}

long long get(long long x, long long b)
{
    long long X = x;

    if(!x)
        return 0;

    string s;
    while(x)
    {
        s.push_back('0' + x % b);
        x /= b;
    }
    x = X;
    reverse(s.begin(), s.end());

    int n = s.size();

    for(int i = 0; i <= n + 1; ++i)
        for(int j = 0; j <= b + 1; ++j)
            dp[i][j] = dp[j][i] = 0;

    dp[b][0] = 1;

    for(int k = b - 1; k > 0; --k)
    {
        for(int i = 0; i <= n; ++i)
            dp[k][i] = dp[k + 1][i];

        for(int to = 0; to <= n; ++to)
            for(int i = 2; i + to <= n; i += 2)
                dp[k][to + i] += dp[k + 1][to] * getCnk(to + i, i);
    }

    for(int i = 0; i <= n; ++i)
        dp[0][i] = dp[1][i];

    for(int to = 1; to <= n; ++to)
        for(int i = 2; i + to <= n; i += 2)
            dp[0][to + i] += dp[1][to] * getCnk(to + i - 1, i);


    long long res = 0;

    for(int i = 2; i < n; i += 2)
        res += dp[0][i];

    if(n % 2 == 0)
    {
        if(good(s, b))
            ++res;

        for(int i = 0; i < b; ++i)
            cnt[i] = 0;

        for(int i = 0; i < s.size(); ++i)
        {
            res += anotherGet(s[i] - '0', b, i, s.size() - 1 - i);
            ++cnt[s[i] - '0'];
        }
    }

    return res;
}

long long solve()
{
    int b;
    long long l, r;
    cin >> b >> l >> r;
    cout << get(r, b) - get(l - 1, b) << '\n';
}

void preprocess(int b)
{
    for(int i = 0; i < 25; ++i)
        for(int j = 0; j < 25; ++j)
            for(int mask = 0; mask < (1 << 10); ++mask)
                dp2[i][j][mask] = 0;

    dp2[b][0][0] = 1;
    for(int k = b - 1; k; --k)
    {
        for(int mask = 0; mask < (1 << 10); ++mask)
        {
            for(int j = 0; j < 25; ++j)
                dp2[k][j][mask] = dp2[k + 1][j][mask];

            int nxtMask = mask;

            for(int to = 0; to < 25; ++to)
                for(int cur = 1; cur + to < 25; ++cur)
                {
                    if(cur & 1)
                        nxtMask = mask | (1 << k);
                    else
                        nxtMask = mask;
                    dp2[k][cur + to][nxtMask] += dp2[k + 1][to][mask] * getCnk(to + cur, cur);
                }
        }
    }
    for(int mask = 0; mask < (1 << 10); ++mask)
    {
        for(int j = 0; j < 25; ++j)
            dp2[0][j][mask] = dp2[1][j][mask];
        int nxtMask = mask;
        for(int to = 1; to < 25; ++to)
            for(int cur = 1; cur + to < 25; ++cur)
            {
                if(cur & 1)
                    nxtMask = mask | (1 << 0);
                else
                    nxtMask = mask;
                dp2[0][cur + to][nxtMask] += dp2[1][to][mask] * getCnk(to + cur - 1, cur);
            }
    }
}

struct T{
    int num, l, r, b;
};

T a[MaxN];

bool cmp(T a, T b)
{
    return a.b < b.b;
}

main()
{
//    freopen("input.txt", "r", stdin);
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);


    int t;
    cin >> t;
    for(int i = 1; i <= t; ++i)
    {
        cin >> a[i].b >> a[i].l >> a[i].r;
        a[i].num = i;
    }
    sort(a + 1, a + t + 1, cmp);
    int l = 1;
    while(l <= t)
    {

        int r = l + 1;
        while(r <= t && a[l].b == a[r].b)
            ++l;

        preprocess(a[l].b);

        for(int i = l; i < r; ++i)
            ans[a[i].num] = get(a[i].r, a[i].b) - get(a[i].l - 1, a[i].b);
        l = r;

    }
    for(int i = 1; i <= t; ++i)
        cout << ans[i] << '\n';
    return 0;
}
