#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int mod = 1e9 + 9;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

int mul(int a, int b){
    return 1LL * a * b % mod;
}

int qpow(int a, int b){
    int ans = 1;
    while(b){
        if (b & 1) ans = mul(ans, a);
        b >>= 1;
        a = mul(a, a);
    }
    return ans;
}

const int maxn = 2e5 + 5;
int fact[maxn], invfact[maxn], pow2[maxn];

void init(){
    pow2[0] = 1;
    for(int i = 1; i < maxn; i++) pow2[i] = pow2[i - 1] * 2 % mod;
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < maxn; i++){
        fact[i] = mul(fact[i - 1], i);
    }
    invfact[maxn - 1] = qpow(fact[maxn - 1], mod - 2);
    for(int i = maxn - 2; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}

int C(int a, int b){
    if (a < 0 or b < 0 or a < b) return 0;
    return mul(fact[a], mul(invfact[b], invfact[a - b]));
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    init();
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        if (m < 30 and (1 << m) < n - m){
            cout << "bankrupt" << '\n';
            continue;
        }
        int p = 1, ans = 0;
        for(int i = 0; i + m <= n; i++){
            int t = C(i + m - 1, m - 1);
            int q = mul(t, qpow(pow2[i + m], mod - 2));
            add(ans, mul(q, pow2[i + m]));
            sub(p, q);
        }
        add(ans, mul(p, pow2[n]));
        cout << ans << '\n';
    }

}