#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const double eps=1e-8;
const int INF=0x3f3f3f3f,mod=1e9+9;

// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif

const int N=100005;
int fact[N],infact[N];
ll qmi(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1)
        res=res*a%p;

        a=a*a%p;
        b>>=1;
    }
    return res;
}
void init(int n)
{
    fact[0]=1;
    for(int i=1;i<=n;i++)
    {
        fact[i]=1ll*fact[i-1]*i%mod;
    }

    infact[n]=qmi(fact[n],mod-2,mod);
    for(int i=n-1;i>=0;i--)
    {
        infact[i]=1ll*infact[i+1]*(i+1)%mod;
    }
}
int C(int n,int m)
{
    if(n<m) return 0;
    return 1ll*fact[n]*infact[m]%mod*infact[n-m]%mod;
}
void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(m<20&&(1<<m)+m<=n)
    {
        puts("bankrupt");
        return ;
    }

    if(m>n)
    {
        printf("%lld\n",qmi(2,n,mod));
        return ;
    }

    int res=C(n,m);
    for(int i=0;i<=m-1;i++)
    {
        res=(res+C(n,i))%mod;
    }
    printf("%d\n",res);
    return ;
}
int main()
{
    init(N-1);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}