#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7, maxn = 40, N = 41;
using u64 = unsigned long long;
inline int add(int a, int b) {return (a += b) >= mod ? a - mod : a;}
inline int sub(int a, int b) {return (a -= b) < 0 ? a + mod : a;}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline void upd(int &a, int b) {a = add(a, b);}
struct Dsu {
	int n;
	vector<int> fa;
	Dsu(int _n) : n(_n), fa(_n + 1) {iota(fa.begin(), fa.end(), 0);}
	void init() {
		iota(fa.begin(), fa.end(), 0);
	}
	int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
	bool merge(int u, int v) {
		u = find(u), v = find(v);
		if(u == v) return false;
		fa[u] = v;
		return true;
	}
};
int ans[N][N], pwr[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int st = clock();
	vector<vector<pair<u64, int>>> _v(N);
	vector<vector<tuple<u64, u64, int>>> _vv(N);
	for(int k = 2; k <= maxn; k ++) {
		pwr[0] = 1;
		for(int i = 1; i <= maxn; i ++) pwr[i] = mul(pwr[i - 1], k);
		vector<vector<pair<u64, int>>> v(N);
		for(int len = 1; len <= maxn; len ++) {
			Dsu dsu(len);
			auto get = [&] (u64 x) {
				int blo = len;
				for(int i = 1; i <= len; i ++) if(x >> i & 1) {
					for(int j = 1; j <= i; j ++) {
						dsu.merge(j, j - i + len);
					}
				}
			};
			auto calc = [&] (u64 x) {
				dsu.init();
				get(x);
				int blo = 0;
				for(int i = 1; i <= len; i ++) blo += dsu.find(i) == i;
				return pwr[blo];
			};
			function<void(int, u64)> dfs = [&] (int p, u64 s) {
				if(p == len) v[len].emplace_back(s, 0);
				for(int i = p + 1; i <= len; i ++) {
					if((i >= 2 * p) || (s >> 2 * p - i & 1)) {
						dfs(i, s | 1ull << i);
					}
				}
			};
			if(_v[len].empty()) dfs(0, 0), _v[len] = v[len];
			else v[len] = _v[len];
			for(auto &[s, k] : v[len]) k = calc(s);
			sort(v[len].begin(), v[len].end()), reverse(v[len].begin(), v[len].end());
			vector<pair<u64, int>> rv;
			for(auto &[s1, k1] : v[len]) {
				for(auto [s2, k2] : rv) {
					if((s1 & s2) == s1) {
						upd(k1, mod - k2);
					}
				}
				if(k1) rv.emplace_back(s1, k1);
			}
			for(int j = len; j <= maxn; j ++) upd(ans[j][k], mul(pwr[j], pwr[len]));
			v[len] = rv;
			for(auto [s, val] : rv) {
				vector<int> f(N);
				f[0] = 1;
				for(int i = 0; i <= maxn; i ++) {
					if(i >= len) {
						for(int j = 1; j < len; j ++) if((s >> j & 1) && i + len - j <= maxn)  upd(f[i + len - j], mod - f[i]);
					}
					for(int j = len + i; j <= maxn; j ++) {
						upd(f[j], mod - mul(f[i], pwr[j - i - len]));
					}
					for(int j = max(i, len); j <= maxn; j ++) upd(ans[j][k], mul(val, mod - mul(pwr[j - i], f[i])));
					for(int j = max(i, len + 1); j <= maxn; j ++) upd(ans[j][k], mul(val, mul(k, mul(pwr[j - i], f[i]))));
				}
			}
		}
		for(int len = 2; len <= maxn; len ++) {
			Dsu dsu(len);
			vector<tuple<u64, u64, int>> vv;
			if(!_vv[len].empty() && k > 2) {
				vv = _vv[len];
			}
			else {
				for(auto [s1, k1] : v[len]) {
					dsu.init();
					for(int i = 1; i <= len; i ++) if(s1 >> i & 1) {
						for(int j = 1; j <= i; j ++) dsu.merge(j, j + len - i);
					}
					u64 t = 0;
					for(int i = 2; i <= len; i ++) {
						int flag = 1;
						for(int j = 2; j <= i; j ++) flag &= dsu.find(j) == dsu.find(j + len - i);
						if(flag) t |= 1ull << i - 1;
					}
					for(auto [s2, k2] : v[len - 1]) if((s2 & t) == t) {
						dsu.init();
						for(int i = 1; i <= len; i ++) if(s1 >> i & 1) {
							for(int j = 1; j <= i; j ++) dsu.merge(j, j + len - i);
						}
						for(int i = 1; i < len; i ++) if(s2 >> i & 1) {
							for(int j = 1; j <= i; j ++) dsu.merge(j + 1, j + len - i);
						}
						int ok = 1;
						for(int i = 1; i <= len; i ++) if(!(s1 >> i & 1)) {
							int flag = 1;
							for(int j = 1; j <= i; j ++) flag &= dsu.find(j) == dsu.find(j + len - i);
							if(flag) {ok = 0; break;}
						}
						for(int i = 1; i < len; i ++) if(!(s2 >> i & 1)) {
							int flag = 1;
							for(int j = 1; j <= i; j ++) flag &= dsu.find(j + 1) == dsu.find(j + len - i);
							if(flag) {ok = 0; break;}
						}
						if(ok) vv.emplace_back(s1, s2, 0);
					}
				}
				_vv[len] = vv;
			}
			// cerr << vv.size() << '\n';
			sort(vv.begin(), vv.end()), reverse(vv.begin(), vv.end());
			for(auto &[s1, s2, k] : vv) {
				dsu.init();
				for(int i = 1; i <= len; i ++) if(s1 >> i & 1) {
					for(int j = 1; j <= i; j ++) dsu.merge(j, j + len - i);
				}
				for(int i = 1; i < len; i ++) if(s2 >> i & 1) {
					for(int j = 1; j <= i; j ++) dsu.merge(j + 1, j + len - i);
				}
				int cnt = 0;
				for(int i = 1; i <= len; i ++) cnt += dsu.find(i) == i;
				k = pwr[cnt];
			}
			vector<tuple<u64, u64, int>> rvv;
			for(auto &[s1, s2, k1] : vv) {
				for(auto [s3, s4, k2] : rvv) {
					if((s1 & s3) == s1 && (s2 & s4) == s2) {
						upd(k1, mod - k2);
					}
				}
				if(k1) rvv.emplace_back(s1, s2, k1); 
			}
			for(auto [s1, s2, val] : rvv) {
				vector<int> f(N);
				f[0] = 1;
				int sum = 0;
				for(int i = 0; i <= maxn; i ++) {
					if(i >= len - 1) {
						for(int j = 1; j < len; j ++) if(s1 >> j & 1) {
							if(i + len - j <= maxn) upd(f[i + len - j], f[i]);
						}
						for(int j = 1; j < len - 1; j ++) if(s2 >> j & 1) {
							if(i + len - j - 1 <= maxn) upd(f[i + len - 1 - j], mod - f[i]);
						}
					}
					for(int j = len + i; j <= maxn; j ++) {
						upd(f[j], mul(f[i], pwr[j - i - len]));
					}
					for(int j = len + i - 1; j <= maxn; j ++) {
						upd(f[j], mod - mul(f[i], pwr[j - i - len + 1]));
					}
					for(int j = max(i, len); j <= maxn; j ++) upd(ans[j][k], mod - mul(f[i], mul(val, pwr[j - i])));
				}
			}
		}
		for(int i = 1; i <= maxn; i ++) upd(ans[i][k], pwr[i]);
	}
	for(int i = 1; i <= maxn; i ++) ans[i][1] = i + 1;	

	int T;
	for(cin >> T; T; T --) {
		int n, k;
		cin >> n >> k;
		cout << ans[n][k] << '\n';
	}
	cerr << 1.0 * (clock() - st) / CLOCKS_PER_SEC << '\n';
	return 0;
}