#include<bits/stdc++.h>
#define rep(l,r) for(int i=l;i<=r;i++)
#define jrep(l,r) for(int j=l;j<=r;j++)
#define rrep(r,l) for(int i=r;i>=l;i--)

#define clz __builtin_popcount

using namespace std;

typedef long long ll;
const int N=1.2e5,mod=1e9+9,P=100000,inv2=(mod+1)>>1;

int n,m;
int fac[N],ifac[N];

int qmi(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=(ll)res*a%mod;
		a=(ll)a*a%mod;
		b>>=1;
	}
	return res;
}

int inv(int a)
{
	return qmi(a,mod-2);
}

int C(int a,int b)
{
	return (ll)fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	fac[0]=1;
	rep(1,P)fac[i]=(ll)fac[i-1]*i%mod;
	ifac[P]=inv(fac[P]);
	rrep(P-1,0)ifac[i]=ifac[i+1]*(i+1ll)%mod;
	
	int T;cin>>T;
	while(T--)
	{
		cin>>n>>m;
		int tt=min(m,30);
		if((1<<tt)<n-m)
		{
			cout<<"bankrupt\n";
			continue;
		}
		else
		{
			m=min(m,n);
			int res=0;
			rep(0,m)res=(res+C(n,i))%mod;
			cout<<res<<'\n';
		}
		
	}
	
	return 0;
}