#include <bits/stdc++.h>

using namespace std;

const int N = 256;

int c[N], d[4];

int ksm(int x, int y, int P) {
    int res = 1;
    while (y) {
        if (y & 1) res = 1ll * res * x % P;
        x = 1ll * x * x % P;
        y >>= 1;
    }
    return res;
}

int solve(int mod) {
    int s = 0, n = 0;
    for (int i = 0; i < N; ++i) s += 1ll * c[i] * i % mod, n += c[i];
    s %= mod;
    if (!s) return 0;
    int fac = 1;
    for (int i = 1; i <= n && fac; ++i) fac = fac * i % (mod - 1);
    return ksm(s, fac, mod);
}

int dp[1 << 11][257];
bitset<257> f[605], g[605];

int calc() {
    int n = 0, mx = 0;
    for (int i = 0; i < N; ++i) n += c[i], mx = max(mx, c[i]);
    if (n <= 11) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        vector<int> o;
        for (int i = 0; i < N; ++i) {
            for (int j = 1; j <= c[i]; ++j) o.push_back(i);
        }
        for (int i = 1; i < 1 << n; ++i) {
            int od = __builtin_parity(i);
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) {
                    for (int k = 0; k < 257; ++k) {
                        int nw = (od ? k - o[j] + 257: k + o[j]) % 257;
                        dp[i][k] += dp[i ^ (1 << j)][nw];
                    }
                }
            }
        }
        int res = 1;
        for (int i = 0; i < 257; ++i) res = 1ll * res * ksm(i, dp[(1 << n) - 1][i], 257) % 257;
        return res;
    }
    if (n - mx > 600) return 0;
    f[0].reset();
    f[0][0] = 1;
    vector<int> o;
    int tmx;
    for (int i = 0; i < N; ++i) if (c[i] == mx) tmx = i;
    for (int i = 0; i < N; ++i) {
        if (i != tmx) for (int j = 1; j <= c[i]; ++j) o.push_back(i);
    }
    for (int i = 0; i < (int)o.size(); ++i) {
        int x = o[i];
        for (int j = 0; j <= i + 1; ++j) g[j].reset();
        for (int j = 0; j <= i; ++j) {
            g[j] |= f[j] << x;
            g[j] |= f[j] >> (257 - x);
            x = (257 - x) % 257;
            g[j + 1] |= f[j] << x;
            g[j + 1] |= f[j] >> (257 - x);
            x = (257 - x) % 257;
        }
        for (int j = 0; j <= i + 1; ++j) f[j] = g[j];
    }
    for (int i = max(n / 2 - (int)o.size(), 0); i <= mx && i <= n / 2; ++i) {
        for (int j = 0; j < 257; ++j) {
            if (f[n / 2 - i][j] && (j + 1ll * (mx - i) * tmx + 1ll * i * (257 - tmx)) % 257 == 0) return 0;
        }
    }
    return 1;
}

signed main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        fill(c, c + 256, 0);
        for (int i = 1, x, y; i <= n; ++i) scanf("%d%d", &x, &y), c[x] += y;
        d[0] = solve(3), d[1] = solve(5), d[2] = solve(17), d[3] = calc();
        for (int i = 0; ; ++i) {
            if (i % 3 == d[0] && i % 5 == d[1] && i % 17 == d[2] && i % 257 == d[3]) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}