#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9;
#define ll long long
inline int ksm(int x,int y)
{
    int ans=1;
    for (;y;y/=2,x=(ll)x*x%mod)
        if (y&1)
            ans=(ll)ans*x%mod;
    return ans;
}
const int N=100005;
int fac[N],inv[N];
int n,m;
int C(int x,int y)
{
    return (ll)fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void solve()
{
    scanf("%d%d",&n,&m);
    if (m<=30)
    {
        int x=1<<30;
        if (x<(n-m))
        {
            puts("bankrupt");
            return;
        }
    }
    int ans=0;
    for (int i=0;i<=m;++i)
        (ans+=C(n,i))%=mod;
    printf("%d\n",ans);
}
void prework()
{
    n=100000;
    fac[0]=1;
    for (int i=1;i<=n;++i)
        fac[i]=(ll)fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2);
    for (int i=n;i;--i)
        inv[i-1]=(ll)inv[i]*i%mod;
}
int main()
{
    int t;
    prework();
    scanf("%d",&t);
    while (t--)
        solve();
    return 0;
}