// Program written by EricWu ~~~
#include <bits/stdc++.h>
 
#define lowbit(x) (x & -x)
 
using namespace std;
 
inline char gc(void) {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
 
#define gc() getchar()
 
template <class T> inline void read(T &x) {
    T f = 1; x = 0; static char c = gc();
    for (; !isdigit(c); c = gc()) if (c == '-') f = -f;
    for (; isdigit(c); c = gc()) x = x * 10 + (c & 15);
    if (f == -1) x = -x;
}
 
inline void readstr(char *s) {
    do *s = gc(); while ((*s == ' ') || (*s == '\n') || (*s == '\r'));
    do *(++s) = gc(); while ((~*s) && (*s != ' ') && (*s != '\n') && (*s != '\r'));
    *s = 0; return;
}
 
inline void readch(char&x) { while (isspace(x = gc())); }
 
char pf[100000], *o1 = pf, *o2 = pf + 100000;
#define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
template <class T>
inline void println(T x, char c = '\n') {
    if (x < 0) ot(45), x = -x;
    static char s[15], *b; b = s;
    if (!x) *b ++= 48;
    for (; x; * b ++= x % 10 + 48, x /= 10);
    for (; b-- != s; ot(*b)); ot(c);
}
 
template <class T> inline void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
 
template <class T> inline void writeln(T x, char c = '\n') { write(x); putchar(c); }
template <class T> inline void chkmax(T &x, const T y) { x > y ? x = x : x = y; }
template <class T> inline void chkmin(T &x, const T y) { x < y ? x = x : x = y; }
 
#define Ms(arr, opt) memset(arr, opt, sizeof(arr))
#define Mp(x, y) make_pair(x, y)
#define endl '\n'

typedef long long ll;
typedef pair <int, int> pii;
typedef array<int, 3> piii;
using i64 = long long;
const i64 inf = 1e18;

const double eps = 1e-10;
const long double PI = acos(-1.0);
const int mod = 1e9 + 7;
struct Point {
    i64 x, y;
    Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
    Point& operator=(const Point &p) {
        this->x = p.x; this->y = p.y;
        return *this;
    }
};
ostream& operator<<(ostream &os, const Point &p) {return os << p.x << " " << p.y;}
typedef Point Vector;

Vector operator+(const Vector &p1, const Vector &p2) {return Vector(p1.x + p2.x, p1.y + p2.y);}
Vector operator-(const Vector &p1, const Vector &p2) {return Vector(p1.x - p2.x, p1.y - p2.y);}
bool operator==(const Point &p1, const Point &p2) {return p1.x == p2.x && p1.y == p2.y;}
bool operator<(const Point &p1, const Point &p2) {return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);}
    
__int128_t Cross(const Vector &a, const Vector &b) {return (__int128_t)a.x * (__int128_t)b.y - (__int128_t)a.y * (__int128_t)b.x;}
double Dist(const Point &a, const Point &b) {
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}
__int128_t Dist2(const Point &a, const Point &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
Vector Rotate(const Vector &a, const double rad) {
    return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
}
int Dot(const Vector &a, const Vector &b) { return a.x * b.x + a.y * b.y;}
double Length(const Vector& a) {return sqrt(1.0 * Dot(a, a)); }
double Angle(const Vector &a, const Vector &b) {
    return asin(Cross(a, b) / Length(a) / Length(b));
}
int dcmp(long double a) {if (fabs(a) <= eps) return 0; return a > 0 ? 1 : -1;}
__int128_t Area(const Point &a, const Point &b, const Point &c) {
    Vector u = a - b, v = a - c;
    auto res = Cross(u, v);
    if (res < 0) return -res;
    return res;
}

void solve() {
    int n; read(n);
    vector<int> val(2 * n + 1);
    for (int i = 1;i <= n;i++) read(val[i]);
    for (int i = n + 1;i <= 2 * n;i++) val[i] = val[i - n];

    vector<Point> p(2 * n + 1);
    for (int i = 1;i <= n;i++) read(p[i].x), read(p[i].y);
    for (int i = n + 1;i <= 2 * n;i++) p[i] = p[i - n];
    vector dp(2 * n + 1, vector<__int128_t>(2 * n + 1, -inf));
    vector<int> R(2 * n + 1, 0);
    vector<int> L(2 * n + 1, 1e9);
    __int128_t ans = 0;
    for (int len = 1;len <= n;len++) {
        if (len == 1) { 
            for (int i = 1;i <= 2 * n;i++) dp[i][i] = 0, R[i] = i, L[i] = i;
        } else {
            for (int i = 1;i + len - 1 <= 2 * n;i++) {
                int j = i + len - 1;
                if (val[i] != val[j]) continue;
                for (int l = i + 1;R[l] <= i + len - 1 && l <= i + len - 1;l++) {
                    chkmax(dp[i][j], dp[l][R[l]] + Area(p[i], p[l], p[R[l]]) + Area(p[i], p[R[l]], p[j]));
                    chkmax(ans, dp[i][j]);
                    // if (dp[i][j] != -inf) {
                    //     cout << "here1 "; writeln(dp[i][j], ' '), writeln(dp[l][R[l]]);
                    //     cout << i << " " << j << " " << l << " " << R[l] << endl; 
                    // } 
                }

                for (int r = i + len - 1 - 1;L[r] >= i + 1;r--) {
                    chkmax(dp[i][j], dp[L[r]][r] + Area(p[i], p[r], p[L[r]]) + Area(p[i], p[r], p[j]));
                    chkmax(ans, dp[i][j]);
                    // if (dp[i][j] != -inf) {
                    //     cout << "here2 "; writeln(dp[i][j], ' '), writeln(dp[L[r]][r]);
                    //     cout << i << " " << j << " " << r << " " << L[r] << endl; 
                    // } 
                }
            }

            for (int i = 1;i + len - 1 <= 2 * n;i++) {
                for (int j = R[i];j <= i + len - 1;j++) {
                    if (val[i] != val[j]) continue;
                    if (dp[i][j] != -inf) chkmax(R[i], j);
                }
                for (int j = L[i];j >= i - len + 1 && j >= 1;j--) {
                    if (val[i] != val[j]) continue;
                    if (dp[j][i] != -inf) chkmin(L[i], j);
                }
            }
        }
    }
    writeln(ans);
}

int main() {
    int T = 1; read(T);
    while (T--) solve();
    // system("pause");
    return 0;
}