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 ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ll long long
#define bs ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define sqr(a) ((a)*(a))
#define all(a) a.begin(),a.end()
//#define endl '\n'
#define y1 y12312123
#define int ll

using namespace std;

const int N=2e5+3;
const int inf=1e9+3;
const int md=1e9+3;
const ll linf=1e18+3;
const double eps=0.000000000000001;

int q,b,l,r;

string sl,sr;

int dp[11][10][20][(1<<10)];
int dp2[11][10][20][(1<<10)];
int dp1[20][(1<<10)][2];
int a[20],n;

string s;

void calc()
{
    memset(dp1,0,sizeof(dp1));
    n=s.size();
    for(int i=0;i<n;++i)
    {
        a[i]=s[i]-'0';
    }

    dp1[0][(1<<a[0])][1]=1;

    for(int j=1;j<(a[0]);++j)
    {
        dp1[0][(1<<j)][0]=1;
    }

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

    for(int i=0;i<n-1;++i)
    {
        for(int j=0;j<(1<<b);++j)
        {
            for(int k=0;k<a[i+1];++k)
            {
                dp1[i+1][j^(1<<k)][0]+=dp1[i][j][0]+dp1[i][j][1];
            }
            dp1[i+1][j^(1<<a[i+1])][1]+=dp1[i][j][1];
            dp1[i+1][j^(1<<a[i+1])][0]+=dp1[i][j][0];
            for(int k=a[i+1]+1;k<b;++k)
            {
                dp1[i+1][j^(1<<k)][0]+=dp1[i][j][0];
            }
        }
    }
}

void calc2()
{
    memset(dp1,0,sizeof(dp1));
    n=s.size();
    for(int i=0;i<n;++i)
    {
        a[i]=s[i]-'0';
    }

    dp1[0][(1<<a[0])][1]=1;

    for(int j=0;j<(a[0]);++j)
    {
        dp1[0][(1<<j)][0]=1;
    }

    for(int i=0;i<n-1;++i)
    {
        for(int j=0;j<(1<<b);++j)
        {
            for(int k=0;k<a[i+1];++k)
            {
                dp1[i+1][j^(1<<k)][0]+=dp1[i][j][0]+dp1[i][j][1];
            }
            dp1[i+1][j^(1<<a[i+1])][1]+=dp1[i][j][1];
            dp1[i+1][j^(1<<a[i+1])][0]+=dp1[i][j][0];
            for(int k=a[i+1]+1;k<b;++k)
            {
                dp1[i+1][j^(1<<k)][0]+=dp1[i][j][0];
            }
        }
    }
}

int get(string s,int v,int g)
{

    if(s.size()==0)return 0;
    int res=0;

    if(g)
    res+=dp[b][s[0]-'0'][s.size()][v];
    else res+=dp2[b][s[0]-'0'][s.size()][v];
    cout<<s<<" "<<v<<" "<<g<<" "<<res<<endl;

    v^=(1<<(s[0]-'0'));

    s.erase(0,1);

    if(s.size()!=0)res+=get(s,v,false);

    return res;
}

main()
{
    bs

    for(int i=2;i<=10;++i)
    {
        b=i;
        for(int j=1;j<=18;++j)
        {
            for(int k=1;k<b;++k)
            {
                s="0";
                s[0]+=k;
                for(int z=1;z<j;++z)
                {
                    s+="0";
                }
                calc();
                for(int z=0;z<(1<<b);++z)
                {
                    dp[i][k][j][z]=dp1[n-1][z][0]+dp1[n-1][z][1];
                }
                calc2();
                for(int z=0;z<(1<<b);++z)
                {
                    dp2[i][k][j][z]=dp1[n-1][z][0];
                }
            }
        }
    }

    cin>>b>>l>>r;
    l--;
    sl="";
    sr="";
    while(l>0)
    {
        sl+="0";
        sl[sl.size()-1]+=l%b;
        l/=b;
    }
    reverse(all(sl));

    while(r>0)
    {
        sr+="0";
        sr[sr.size()-1]+=r%b;
        r/=b;
    }
    reverse(all(sr));
    cout<<sl<<" "<<sr<<endl;
    cout<<get(sr,0,true)-get(sl,0,true)<<endl;
    return 0;

    cin>>q;
    for(int i=1;i<=q;++i)
    {
        cin>>b>>l>>r;
        l--;
        sl="";
        sr="";
        while(l>0)
        {
            sl+="0";
            sl[sl.size()-1]+=l%b;
            l/=b;
        }
        reverse(all(sl));

        while(r>0)
        {
            sr+="0";
            sr[sr.size()-1]+=r%b;
            r/=b;
        }
        reverse(all(sr));

        cout<<get(sr,0,true)-get(sl,0,true)<<endl;

    }
}
/*
9 71 169
*/
