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

long long dp1[509][509];
long long dp2[509][509];

long long Solve(int N, vector<long long> V, vector<long long> X, vector<long long> Y) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) dp1[i][j] = -(1LL << 60);
		for (int j = 0; j < N; j++) dp2[i][j] = -(1LL << 60);
	}
	for (int i = 0; i < N; i++) dp1[i][i] = 0;

	// Get Answer
	for (int haba = 0; haba < N; haba++) {
		for (int l = 0; l < N; l++) {
			int r = (l + haba) % N;

			// Step 1
			for (int more = 1; more < N - haba; more++) {
				int next_l = l - more; if (next_l < 0) next_l += N;
				// if (next_l == 4 && l == 5) cout << (X[next_l] - X[l]) * (Y[next_l] + Y[l]) << endl;
				dp2[next_l][r] = max(dp2[next_l][r], dp1[l][r] + (X[next_l] - X[l]) * (Y[next_l] + Y[l]));
			}

			// Step 2
			for (int more = 1; more < N - haba; more++) {
				int next_r = r + more; if (next_r >= N) next_r -= N;
				if (V[l] != V[next_r]) continue;
				// if (next_r == 7 && r == 5) cout << l << " " << r << " " << (X[r] - X[next_r]) * (Y[r] + Y[next_r]) << " " << dp2[l][r] << endl;
				dp1[l][next_r] = max(dp1[l][next_r], dp2[l][r] + (X[r] - X[next_r]) * (Y[r] + Y[next_r]));
			}
		}
	}
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) printf("% 4lld", max(-99LL, dp1[i][j]));
		printf("\n");
	}*/

	// Get Maximum
	long long Answer = 0;
	for (int haba = 0; haba < N; haba++) {
		for (int l = 0; l < N; l++) {
			int r = (l + haba) % N;
			long long ret = (X[r] - X[l]) * (Y[r] - Y[l]);

			// Brute Force
			for (int i = 1; i < N - haba; i++) {
				int m = (r + i) % N;
				long long r1 = (X[m] - X[l]) * (Y[m] - Y[l]);
				long long r2 = (X[r] - X[m]) * (Y[r] - Y[m]);
				ret = max(ret, r1 + r2);
			}
			Answer = max(Answer, ret + dp1[l][r]);
		}
	}

	// Return
	return Answer;
}

int main() {
	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		int N; cin >> N;
		vector<long long> V(N, 0);
		vector<long long> X(N, 0);
		vector<long long> Y(N, 0);
		for (int i = 0; i < N; i++) cin >> V[i];
		for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
		cout << Solve(N, V, X, Y) << endl;
	}
	return 0;
}