#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void chk_max(ll &x, ll y) {
	if (x < y) {
		x = y;
	}
}

void solve() {
	int n;
	cin >> n;
	vector<int> f(n);
	for (int &x : f) {
		cin >> x;
	}
	vector<ll> x(n), y(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	f.insert(f.end(), f.begin(), f.end());
	x.insert(x.end(), x.begin(), x.end());
	y.insert(y.end(), y.begin(), y.end());
	auto cross = [&](int i, int j) {
		return x[i] * y[j] - y[i] * x[j];
	};
	vector dp(2 * n, vector<ll>(2 * n, LLONG_MIN)), dp2(dp);
	for (int i = 0; i < 2 * n; i++) {
		dp[i][i] = 0;
	}
	ll ans = 0;
	for (int len = 0; len <= n; len++) {
		for (int l = 0, r = len; r < 2 * n; l++, r++) {
			if (dp[l][r] != LLONG_MIN) {
				chk_max(ans, dp[l][r] + cross(r, l));
				for (int i = 0; i < l; i++) {
					chk_max(dp2[i][r], dp[l][r] + cross(i, l));
				}
			}
			if (dp2[l][r] != LLONG_MIN) {
				for (int i = r + 1; i < 2 * n; i++) {
					if (f[l] == f[i]) {
						chk_max(dp[l][i], dp2[l][r] + cross(r, i));
					}
				}
			}
		}
	}
	cout << ans << "\n";
}

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