#include <bits/stdc++.h>
#define li long long int
#define MOD 1000000009
using namespace std;
li expo(li base, li expo)
{
    li res = 1;
    while (expo)
    {
        if(expo%2 == 1)  res = (res*base)%MOD;
        base = (base*base)%MOD;
        expo /=2;
    }
    return res;
}
int main()
{
    li t,s,x,res,K;
    cin >> t;
    while ( t-- )
    {
        cin >> x >> s;
        K = s/(x*x);
        res = expo(K,x*x);
        cout << res << endl;
    }
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGkgbG9uZyBsb25nIGludAojZGVmaW5lIE1PRCAxMDAwMDAwMDA5CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmxpIGV4cG8obGkgYmFzZSwgbGkgZXhwbykKewogICAgbGkgcmVzID0gMTsKICAgIHdoaWxlIChleHBvKQogICAgewogICAgICAgIGlmKGV4cG8lMiA9PSAxKSAgcmVzID0gKHJlcypiYXNlKSVNT0Q7CiAgICAgICAgYmFzZSA9IChiYXNlKmJhc2UpJU1PRDsKICAgICAgICBleHBvIC89MjsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KaW50IG1haW4oKQp7CiAgICBsaSB0LHMseCxyZXMsSzsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKCB0LS0gKQogICAgewogICAgICAgIGNpbiA+PiB4ID4+IHM7CiAgICAgICAgSyA9IHMvKHgqeCk7CiAgICAgICAgcmVzID0gZXhwbyhLLHgqeCk7CiAgICAgICAgY291dCA8PCByZXMgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==

MgoyIDQKMiAxNg==

2
2 4
2 16