#include <bits/stdc++.h>

#define fo(i, x, y) for (int i = int(x); i <= int(y); ++i)
#define fd(i, x, y) for (int i = int(x); i >= int(y); --i)
#define fi first
#define se second

using namespace std;
using pii = pair<int, int>;
using i64 = long long;

constexpr int P = 1e9 + 9;
constexpr int N = 1e6 + 5;

template <class T>
T power(T a, int b)
{
	T res = 1;
	for (; b; b >>= 1, a *= a)
		if (b & 1)
			res *= a;
	return res;
}

int nor(int x)
{
	if (x < 0) x += P;
	if (x >= P) x -= P;
	return x;
}
struct Z
{
	int x;
	Z(i64 x = 0) : x(nor(x % P)) {}
	int val() const
	{
		return x;
	}
	Z operator-() const
	{
		return Z(nor(P - x));
	}
	Z inv() const
	{
		assert(x != 0);
		return power(*this, P - 2);
	}
	Z &operator*=(const Z &rhs)
	{
		x = i64(x) * rhs.x % P;
		return *this;
	}
	Z &operator+=(const Z &rhs)
	{
		x = nor(x + rhs.x);
		return *this;
	}
	Z &operator-=(const Z &rhs)
	{
		x = nor(x - rhs.x);
		return *this;
	}
	Z &operator/=(const Z &rhs)
	{
		return *this *= rhs.inv();
	}
	friend Z operator*(const Z &lhs, const Z &rhs)
	{
		Z res = lhs;
		res *= rhs;
		return res;
	}
	friend Z operator+(const Z &lhs, const Z &rhs)
	{
		Z res = lhs;
		res += rhs;
		return res;
	}
	friend Z operator-(const Z &lhs, const Z &rhs)
	{
		Z res = lhs;
		res -= rhs;
		return res;
	}
	friend Z operator/(const Z &lhs, const Z &rhs)
	{
		Z res = lhs;
		res /= rhs;
		return res;
	}
	friend istream& operator>>(istream& is, Z& a)
	{
		i64 v;
		is >> v;
		a = Z(v);
		return is;
	}
	friend ostream& operator<<(ostream& os, const Z& a)
	{
		return os << a.val();
	}
};

Z fac[N], ifac[N];

void init(int n)
{
	fac[0] = 1;
	fo(i, 1, n)
		fac[i] = fac[i - 1] * i;
	ifac[n] = 1 / fac[n];
	fd(i, n - 1, 0)
		ifac[i] = ifac[i + 1] * (i + 1);
}

Z C(int n, int m)
{
	return fac[n] * ifac[n - m] * ifac[m];
}

void work()
{
	int n, m;
	cin >> n >> m;
	i64 t = 1;
	bool ok = false;
	fo(i, 1, m)
	{
		t <<= 1;
		if (t >= n - m)
		{
			ok = true;
			break;
		}
	}
	if (!ok)
	{
		cout << "bankrupt\n";
		return;
	}
	Z ans = C(n, m);
	fo(i, 0, m - 1)
		ans += C(n, i);
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
#ifdef LC
	freopen("t.in", "r", stdin);
	freopen("t.out", "w", stdout);
#endif
	init(200000);
	int T;
	cin >> T;
	while (T--)
		work();
	return 0;
}