#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#define int long long

using namespace std;

const int p=;

int T,c[p+][p+],sum[p+][p+];

int Lucas(int a,int b)

{

    if(a<||b<) return ;

    if(a<p&&b<p) return c[a][b];

    return Lucas(a/p,b/p)*c[a%p][b%p]%p;

}

int cal(int n,int k)

{

    if(k<) return ;

    return (cal(n/p,k/p-)*sum[n%p][p-]+Lucas(n/p,k/p)*sum[n%p][k%p])%p;

}

void pre()

{

    c[][]=;sum[][]=; for(int i=;i<p;i++) c[i][]=,sum[i][]=,sum[][i]=;

    for(int i=;i<p;i++) for(int j=;j<=i;j++) c[i][j]=(c[i-][j-]+c[i-][j])%p;

    for(int i=;i<p;i++) for(int j=;j<p;j++) sum[i][j]=sum[i][j-]+c[i][j];

}

signed main()

{

    pre();

    scanf("%lld",&T);

    while(T--)

    {

        int n,k;

        scanf("%lld%lld",&n,&k);

        printf("%lld\n",cal(n,k));

    }

    return ;

}