#include<bits/stdc++.h>
using namespace std;
const int p=10007;
int ksm(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
int C(int a,int b){
    int res=1;
    for(int i=1,j=a;j>=1,i<=b;j--,i++){//666
        res=res*j%p;
        res=res*ksm(i,p-2,p)%p;
    }
    return res;
}
int lcs(int a,int b){
    if(a>=p&&b>=p)
    return lcs(a/p,b/p)*C(a%p,b%p)%p;
    return C(a,b);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
      cout<<lcs(a,b)<<endl;
    }
    return 0;
}