#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define otto auto
const int MAXN=1e6+10;
const int INF=1ll*1e7*1e9;
const int MOD = 1e9 + 9;
int T,N,M,K,P,Q;


struct Math_class{
	static const int MAXN = 1e6 + 10;
	int fac[MAXN],facInv[MAXN];
	bool fac_ini = false;
	bool prime_ini = false;

	void getFac(int n = MAXN){
		fac_ini = true;
		fac[0] = 1;
		for(int i=1;i<n;i++) fac[i] = fac[i-1] * i % MOD;
		facInv[n-1] = inv(fac[n-1]);
		for(int i=n-2;i>=0;i--) facInv[i] = facInv[i+1] * (i+1) % MOD;
	}

	int C(int n,int m){
		assert(fac_ini);
		if(m > n || m < 0) return 0;
		return fac[n]*facInv[m]%MOD*facInv[n-m]%MOD;
	}
	int A(int n,int m){
		assert(fac_ini);
		if(m > n || m < 0) return 0;
		return fac[n]*facInv[n-m]%MOD;
	};

	bool is_prime[MAXN];
	vector<int> prime;
	void getPrime(int n = MAXN){
		prime_ini = true;
		for(int i=2;i<n;i++) is_prime[i] = true;
		for(int i=2;i<n;i++){
			if(is_prime[i]){
				prime.push_back(i);
				for(int j=2*i;j<n;j+=i) is_prime[j] = false;
			}
		}
	}

	int quick_pow(int x,int k){
		int ret = 1; x %= MOD;
		while(k){
			if(k&1) ret = ret * x % MOD;
			x = x * x % MOD; k >>= 1;
		}
		return ret;
	}
	int inv(int x){return quick_pow(x,MOD-2);}
}Math;

int p2[MAXN];

void prepare(){
	int ans = 0;
	scanf("%lld %lld",&N,&M);
	if(M <= 20 && p2[M] < N - M){
		printf("bankrupt\n");
		return;
	}
	for(int i = M;i <= N; i++){
		ans = (ans + Math.C(i-1,M-1)) % MOD;
	}
	for(int i = 0;i <= M-1; i++){
		ans = (ans + Math.C(N,i)) % MOD;
	}
	cout<<ans<<endl;
}

signed main(){
	//ios::sync_with_stdio(0);
	T=1;
	Math.getFac();
	p2[0] = 1;
	for(int i = 1;i <= 100000; i++) p2[i] = p2[i-1] * 2 % MOD;
	scanf("%lld",&T);
	while(T--){
	    prepare();
	}
	return 0;
}