#include <bits/stdc++.h>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int P=1000000009;
const int N=100003;
typedef long long ll;
int qp(int a,int b=P-2){
	int res=1;
	while(b){
		if(b&1) res=(ll)res*a%P;
		a=(ll)a*a%P;b>>=1;
	}
	return res;
}
int n,m;
int fac[N],fiv[N];
int C(int n,int k){
	if(k<0||k>n) return 0;
	return (ll)fac[n]*fiv[k]%P*fiv[n-k]%P;
}
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
void solve(){
	n=read();m=read();
	bool fl=1;
	int pw=1;
	for(int i=1;i<=m;++i){
		pw<<=1;
		if(pw>=n-m){fl=0;break;}
	}
	if(fl) return void(puts("bankrupt"));
	int res=0;
	for(int i=0;i<m;++i) inc(res,C(n,i));
	inc(res,C(n,m));
	printf("%d\n",res);
}
int main(){
	fac[0]=1;
	for(int i=1;i<=100000;++i) fac[i]=(ll)fac[i-1]*i%P;
	fiv[100000]=qp(fac[100000]);
	for(int i=100000;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
	int tc=read();
	while(tc--) solve();
	return 0;
}