#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 10007;
int n,m,t;

int po(int a,int b,int p)
{
	int mul = 1;
	while(b)
	{
		if(b & 1) mul = mul * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return mul;
}

int C(int n,int m,int p)
{
    int x = 1,y = 1;
    for(int i = 1;i <= m;i++)
	{
        x = x * (n - i + 1) % p;
        y = y * i % p;
    }
    return x * po(y,p - 2,p) % p;
}
int lucas(int n,int m,int p)
{
	if(!m) return 1;
	return C(n % p,m % p,p) * lucas(n / p,m / p,p) % p;
}
signed main()
{
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		printf("%lld\n",lucas(n,m,mod) % mod);
	}
	return 0;
}