#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

long long solve(int N, const vector<long long>& F, const vector<long long>& X, const vector<long long>& Y) {
	// step #1. calculate area
	auto sub_area = [&](int va, int vb) -> long long {
		return X[va] * Y[vb] - X[vb] * Y[va];
	};

	// step #2. dynamic programming
	const long long INF = 3LL << 59;
	vector<vector<array<long long, 2> > > dp(2 * N, vector<array<long long, 2> >(2 * N, {-INF, -INF}));
	vector<vector<array<int, 2> > > pre(2 * N, vector<array<int, 2> >(2 * N, {-1, -1}));
	for (int i = 0; i < N; i++) {
		dp[i][i + N][1] = 0;
	}
	for (int i = N; i >= 1; i--) {
		for (int l = 0; l < 2 * N - i; l++) {
			int r = l + i;
			if (dp[l][r][0] != -INF) {
				for (int j = l + 1; j <= r; j++) {
					if (dp[j][r][1] < dp[l][r][0] + sub_area(l, j)) {
						pre[j][r][1] = l;
					}
					dp[j][r][1] = max(dp[j][r][1], dp[l][r][0] + sub_area(l, j));
				}
			}
			if (dp[l][r][1] != -INF) {
				for (int j = l; j <= r - 1; j++) {
					if (F[l] == F[j]) {
						if (dp[l][j][0] < dp[l][r][1] + sub_area(j, r)) {
							pre[l][j][0] = r;
						}
						dp[l][j][0] = max(dp[l][j][0], dp[l][r][1] + sub_area(j, r));
					}
				}
			}
		}
	}
	
	// step #3. final answer
	long long ans = 0;
	for (int i = 0; i < 2 * N; i++) {
		ans = max(ans, dp[i][i][0]);
		ans = max(ans, dp[i][i][1]);
	}

	return ans;
}

int main() {
	int T;
	cin >> T;
	for (int id = 1; id <= T; id++) {
		int N;
		cin >> N;
		vector<long long> F(2 * N), X(2 * N), Y(2 * N);
		for (int i = 0; i < N; i++) {
			cin >> F[i];
			F[N + i] = F[i];
		}
		for (int i = 0; i < N; i++) {
			cin >> X[i] >> Y[i];
			X[N + i] = X[i];
			Y[N + i] = Y[i];
		}
		long long ans = solve(N, F, X, Y);
		cout << ans << endl;
	}
	return 0;
}

answer.code: In function ‘long long int solve(int, const std::vector<long long int>&, const std::vector<long long int>&, const std::vector<long long int>&)’:
answer.code:14:105: error: no matching function for call to ‘std::vector<std::array<long long int, 2> >::vector(int, <brace-enclosed initializer list>)’
   14 |         vector<vector<array<long long, 2> > > dp(2 * N, vector<array<long long, 2> >(2 * N, {-INF, -INF}));
      |                                                                                                         ^
In file included from /usr/include/c++/13/vector:66,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_vector.h:704:9: note: candidate: ‘template<class _InputIterator, class> std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with <template-parameter-2-2> = _InputIterator; _Tp = std::array<long long int, 2>; _Alloc = std::allocator<std::array<long long int, 2> >]’
  704 |         vector(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:704:9: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/13/bits/stl_algobase.h:65,
                 from /usr/include/c++/13/vector:62:
/usr/include/c++/13/bits/stl_iterator_base_types.h: In substitution of ‘template<class _InIter> using std::_RequireInputIter = std::__enable_if_t<std::is_convertible<typename std::iterator_traits< <template-parameter-1-1> >::iterator_category, std::input_iterator_tag>::value> [with _InIter = int]’:
/usr/include/c++/13/bits/stl_vector.h:702:9:   required from here
/usr/include/c++/13/bits/stl_iterator_base_types.h:250:11: error: no type named ‘iterator_category’ in ‘struct std::iterator_traits<int>’
  250 |     using _RequireInputIter =
      |           ^~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:675:7: note: candidate: ‘std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = std::array<long long int, 2>; _Alloc = std::allocator<std::array<long long int, 2> >; allocator_type = std::allocator<std::array<long long int, 2> >]’
  675 |       vector(initializer_list<value_type> __l,
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:675:43: note:   no known conversion for argument 1 from ‘int’ to ‘std::initializer_list<std::array<long long int, 2> >’
  675 |       vector(initializer_list<value_type> __l,
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:656:7: note: candidate: ‘std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, std::__type_identity_t<_Alloc>&) [with _Tp = std::array<long long int, 2>; _Alloc = std::allocator<std::array<long long int, 2> >; std::__type_identity_t<_Alloc> = std::allocator<std::array<long long int, 2> >]’
  656 |       vector(vector&& __rv, const __type_identity_t<allocator_type>& __m)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:656:23: note:   no known conversion for argument 1 from ‘int’ to ‘std::vector<std::array<long long int, 2> >&&’
  656 |       vector(vector&& __rv, const __type_identity_t<allocator_type>& __m)
      |              ~~~~~~~~~^~~~
/usr/include/c++/13/bits/stl_vector.h:637:7: note: candidate: ‘std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::false_type) [with _Tp = std::array<long long int, 2>; _Alloc = std::allocator<std::array<long long int, 2> >; allocator_type = std::allocator<std::array<long long int, 2> >; std::false_type = std::integral_constant<bool, false>]’
  637 |       vector(vector&& __rv, const allocator_type& __m, false_type)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:637:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/13/bits/stl_vector.h:632:7: note: candidate: ‘std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::true_type) [with _Tp = std::array<long long int, 2>; _Alloc = std::allocator<std::array<long long int, 2> >; allocator_type = std::allocator<std::array<long long int, 2> >; std::true_type = std::integral_constant<bool, true>]’
  632 |       vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:632:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/13/bits/stl_vector.h:621:7: note: candidate: ‘std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&, std::__type_identity_t<_Alloc>&) [with _Tp = std::array<long long int, 2>; _Alloc = std::allocator<std::array<long long int, 2> >; std::__type_identity_t<_Alloc> = std::allocator<std::array<long long int, 2> >]’
  621 |       vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
      |       ^~~~~~
/usr/include/c++/13/bits/stl_vector.h:621:28: note:   no known conversion for argument 1 from ‘int’ to ‘const std::vector<std::array<long long int, 2> >&’
  621 |       vector(const vector...