#include<cstdio>
using namespace std;
long long a[2401][2401],p=2333ll;
long long minn(long long x,long long y){return x<y?x:y;}
long long zhs(long long x,long long y){
	if(!x||!y)return 1;if(y<0)return 0;
	if(x<p&&y<p)return a[x][y];
	long long z=minn(y%p,x%p),q=zhs(x/p,y/p-1);
	return (q*a[x%p][x%p]%p+(zhs(x/p,y/p)-q+p)*a[x%p][z]%p)%p;
}
int main()
{
	long long i,j,k,m,q,n;
	scanf("%lld",&n);a[0][0]=1;
	for(i=1;i<=p;i++){a[i][0]=1;
		for(j=1;j<=i;j++)a[i][j]=(a[i-1][j]+a[i-1][j-1])%p;
	}for(i=1;i<=p;i++)
		for(j=1;j<=i;j++)a[i][j]=(a[i][j]+a[i][j-1])%p;
	for(k=0;k<n;k++){
		scanf("%lld%lld",&m,&q);
		printf("%lld\n",zhs(m,q));	
	}return 0;
}