#include <bits/stdc++.h>

#define ll long long

const int MAX_N = 1e5 + 10 , mod = 1e9 + 9 ;

int T , n , m , jc[MAX_N] , inv[MAX_N] ;

int qpow(int a , int t) {
	int s = 1 ;
	for (; t ; t >>= 1 , a = (ll)a * a % mod)
		if (t & 1) s = (ll)s * a % mod ;
	return s ;
}

void init() {
	int N = 1e5 ; jc[0] = 1 ;
	for (int i = 1 ; i <= N ; ++i) jc[i] = (ll)jc[i - 1] * i % mod ;
	inv[N] = qpow(jc[N] , mod - 2) ;
	for (int i = N - 1 ; i >= 0 ; --i) inv[i] = (ll)inv[i + 1] * (i + 1) % mod ;
}

inline int C(int n , int m) {
	return (ll)jc[n] * inv[m] % mod * inv[n - m] % mod ;
}

int main() {
	init() ;
	int T ; scanf("%d" , &T) ;
	for (; T-- ;) {
		scanf("%d %d" , &n , &m) ;
		int s = 1 ;
		for (int i = 0 ; i < m ; ++i) {
			s *= 2 ;
			if (s >= n - m) {s = -1 ; break ;}
		}
		if (s != -1) {printf("bankrupt\n") ; continue ;}

		///

		int ans = C(n , m) % mod ;
		for (int i = 0 ; i < m ; ++i) (ans += C(n , i)) %= mod ;
		printf("%d\n" , ans) ;
	}

	return 0 ;
}