#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

#include <cstdio>

typedef long long ll;

using namespace std;

const int mod = ;

        int dp[][][];

        int cnt[],shu[];

        ll swdp(int len, int x,int sum, bool limit){

                if(len == )return ;

                if(!limit && dp[len][x][sum]) return dp[len][x][sum];

                int mx = limit ? shu[len] : ;

                ll res = ;

                for(int i=; i<=mx; i++){

                    if(x==i && sum +  > cnt[x])continue;

                    if(x==i) res = (res + swdp(len-,x,sum+, limit && i == mx)) % mod;

                    else res = (res + swdp (len-,i,,limit && i == mx))%mod;

                }

                return limit?res:dp[len][x  ][sum] = res;

        }

        ll solve(ll x){

            if(x == -)return ;

            int k = ;

            while(x > ){

                shu[++k] = x % ;

                x /= ;

            }

            return swdp(k, , ,  true);

        }

int main(){

        int t,n;  scanf("%d", &t);

        ll le,ri;

        while(t--) {

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

            memset(dp,,sizeof(dp));

            scanf("%lld%lld%d", &le, &ri, &n);

            while(n--) {

                int x,len;

                scanf("%d%d", &x, &len);

                cnt[x] = min(cnt[x] , len);

            }

            printf("%lld\n", (solve(ri) - solve(le-) + mod)%mod);

        }

        return ;

}