#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int p=2333;
int T,c[p+10][p+10],sum[p+10][p+10];
int Lucas(int a,int b)
{
    if(a<0||b<0) return 0;
    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<0) return 0;
    return (cal(n/p,k/p-1)*sum[n%p][p-1]+Lucas(n/p,k/p)*sum[n%p][k%p])%p;
}
void pre()
{
    c[0][0]=1;sum[0][0]=1; for(int i=1;i<p;i++) c[i][0]=1,sum[i][0]=1,sum[0][i]=1;
    for(int i=1;i<p;i++) for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
    for(int i=1;i<p;i++) for(int j=1;j<p;j++) sum[i][j]=sum[i][j-1]+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 0;
}