#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 300, mod1 = 255, mod2 = 257, phi1 = 128, phi2 = 256;
int fpw(int a, int b, int mod) {
	int ans = 1;
	for(; b; b >>= 1, a = 1ll * a * a % mod) if(b & 1) ans = 1ll * ans * a % mod;
	return ans;
}
int cnt[256];
bitset<513> f[257], g[257];
int gogo() {
	int n = 0, mp = 0;
	for (int i = 0; i < 256; ++i) {
		n += cnt[i];
		if (cnt[i] > cnt[mp]) {
			mp = i;
		}
	}
	int mv = cnt[mp];
	assert(mv == *max_element(cnt, cnt + 256));
	if (n >= 512 && n - mv >= 256)
		return 0;
	for (int i = 0; i < 256; ++i)
		f[i].reset();
	f[0].set(0);
	auto gogogo = [&](int k) {
		for (int i = 0; i < 257; ++i)
			g[i] = f[(i + k) % 257] << 1;
		for (int i = 0; i < 257; ++i)
			f[i] |= g[i];
	};
	for (int i = 0; i < 256; ++i)
		if (i != mp) {
			for (int j = 0; j < cnt[i]; ++j) {
				gogogo((257 - cnt[i]) % 257);
			}
		}
	int sum = 0;
	for (int i = 0; i < 256; ++i)
		sum = (sum + 1ll * cnt[i] * i) % 257;
	for (int i = 0; i < 257; ++i)
		for (int j = 0; j <= n - mv; ++j)
			if (f[i][j]) {
				int k = n / 2 - j;
				if (k >= 0 && k <= mv && (2 * (i + 1ll * k * mp)) % 257 == sum)
					return 0;
			}
	return 1;
}
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	for(cin >> T; T; T --) {
		int k, s = 0, n = 0;
		cin >> k;
		memset(cnt, 0, sizeof cnt);
		vector<int> vec;
		for(int i = 0; i < k; i ++) {
			int di, ci;
			cin >> di >> ci;
			cnt[di] = ci;
			s = (s + 1ll * di * ci) % mod1;
			n += ci;
			for(int i = 0; i < ci; i ++) vec.emplace_back(di);
		}
		int facn = 1;
		if(n < 8) {
			for(int i = 1; i <= n; i ++){
				facn = facn * i;
			}
		}
		else facn = 2 * phi1;
		int ans1 = fpw(s, facn, mod1), ans2 = 1;
		// cout << ans1 << '\n';
		if(n < 12) {
			int m = (n + 1) / 2;
			vector<vector<vector<int>>> f(n + 1, vector<vector<int>> (m + 1, vector<int> (mod2)));
			f[0][0][0] = 1;
			// cout << "-----------\n";
			for(int i = 0; i < n; i ++) {
				for(int j = 0; j <= m; j ++) {
					for(int s = 0; s < mod2; s ++) if(f[i][j][s]) {
						if(j < m) f[i + 1][j + 1][(s + vec[i]) % mod2] += f[i][j][s];
						f[i + 1][j][(s - vec[i] + mod2) % mod2] += f[i][j][s];
					}
				}
			}
			int w = 1;
			for(int i = 1; i <= m; i ++) w = w * i;
			for(int i = 1; i <= n - m; i ++) w = w * i;
			// cout << w << '\n';
			for(int i = 0; i < mod2; i ++) if(f[n][m][i]) {
				// cout << i << ": " << w << ' ' << f[n][m][i] << '\n';
				ans2 = 1ll * ans2 * fpw(i, 1ll * f[n][m][i] * w % phi2, mod2) % mod2;
			}
		}
		else {
			ans2 = gogo();
		}
		auto crt = [&] (int m1, int a1, int m2, int a2) {
			int d = a2 - a1, m = m1 * m2;
			int x, y;
			function<void(int, int, int&, int &)> exgcd =[&] (int a, int b, int &x, int &y) {
				if(!b) return x = 1, y = 0, void();
				exgcd(b, a % b, y, x), y -= a / b * x;
			};
			exgcd(m1, m2, x, y);
			x *= d;
			return ((a1 + m1 * x) % m + m) % m;
		};
		cout << crt(mod1, ans1, mod2, ans2) << '\n';
	}
	return 0;
}