4

5 1

5 2

7 3

4 2

5

10

35

6

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll mod=;

inline int read()

{

    int x=,f=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline ll power(ll a,ll b)

{

    ll res=;

    while(b)

    {

        if(b&) res=res*a%mod; a=a*a%mod; b>>=;

    }

    return res;

}

inline ll C(ll n,ll m)

{

    ll n0=,m0=;

    for(ll i=n-m+;i<=n;i++) n0=n0*i%mod;

    for(ll i=;i<=m;i++) m0=m0*i%mod;

    return n0*power(m0,mod-)%mod;

}

inline ll Lucas(ll n,ll m)

{

    if(m==) return ;

    return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;

}

int main()

{

    int t;

    t=read();

    ll n,m;

    while(t--)

    {

        n=(ll)read();

        m=(ll)read();

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

    }

    return ;

}