#include <bits/stdc++.h>
#define dd(x) cout << #x << "\n"
#define d(x) cout << #x  << ": " << x << "\n"
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
const int inf = 0x3f3f3f3f3f3f3f3fLL;

const int mod = 1e9 + 9;
int qpow(int a, int b) {
    int res = 1;
    for (; b; b /= 2, a = a * a % mod) {
        if (b & 1) {
            res = res * a % mod;
        }
    }
    return res;
}
int inv(int a) {
    return qpow(a, mod - 2);
}
// 1-n的逆元
vector<int> linear_inv(int n) {
    vector<int> iv(n + 1);
    iv[1] = 1;
    for (int i = 2; i <= n; i++) {
        iv[i] = (mod - mod / i) * iv[mod % i] % mod;
    } 
    return iv;
}
// 任意n个数的逆元
vector<int> linear_inv(const vector<int> &a) {
    int n = a.size() - 1;
    vector<int> iv(n + 1), s(n + 1), sv(n + 1);
    s[0] = 1;
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] * a[i] % mod;
    }
    sv[n] = inv(s[n]);
    for (int i = n; i >= 1; i--) {
        sv[i - 1] = sv[i] * a[i] % mod;
    }
    for (int i = 1; i <= n; i++) {
        iv[i] = sv[i] * s[i - 1] % mod;
    }
    return iv;
}

int positive(int x) {
    return (x % mod + mod) % mod;
}

void solve() {
    int m, k; cin >> m >> k;
    vector<int> down(k + 1);
    for(int i = 1; i <= k; i++) {
        down[i] = i * m - i + 1;
    }
    down = linear_inv(down);
    vector<int> v(k + 1), dp(k + 1);
    
    for(int i = 1; i <= k; i++) {
        v[i] = positive(v[i - 1] + m * down[i]);
        dp[i] = positive(dp[i - 1] + m * (v[i - 1] + 1));
    }

    cout << dp[k] << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}