#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 20050

#define mod 10007

using namespace std;

long long t,n,m,inv1[maxn],inv2[maxn];

long long f_pow(long long x,long long y)

{

    long long ans=,base=x;

    while (y)

    {

        if (y&) ans=(ans*base)%mod;

        base=(base*base)%mod;

        y>>=;

    }

    return ans%mod;

}

void get_table()

{

    inv1[]=;inv2[]=;

    for (long long i=;i<=;i++)

    {

        inv1[i]=inv1[i-]*i%mod;

        inv2[i]=f_pow(inv1[i],mod-);

    }

}

long long comb(long long n,long long m)

{

    return inv1[n]*inv2[m]%mod*inv2[n-m]%mod;

}

long long lucas(long long n,long long m)

{

    if (!m) return ;

    return comb(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;

}

int main()

{

    get_table();

    scanf("%lld",&t);

    for (long long i=;i<=t;i++)

    {

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

        printf("%lld\n",lucas(n,m));

    }

    return ;

}