#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include <valarray>
#include <cmath>
#include <numeric>
#include <random>
#include <unordered_map>
#include <queue>

using namespace std;

#define ll long long
#define pr pair<int, int>

const int maxN = 5e2+10, mod = 998244353, inf = 1e9+10;
int n;
ll dp1[maxN][maxN], dp2[maxN][maxN];
unordered_map<int, int> last[maxN], fir[maxN];

struct point{
    ll x, y;
    int f;
}p[maxN];

struct vect{
    ll x, y;
};

vect operator-(point x, point y){
    return vect{x.x-y.x, x.y-y.y};
}

ll operator^(vect x, vect y){
    return abs(x.x*y.y-x.y*y.x);
}

ll power(ll x, ll y){
    ll an = 1;
    while (y){
        if (y & 1) an = an*x % mod;
        x = x*x % mod;
        y >>= 1;
    }
    return an;
}

ll cal(point& x, point& y, point& z, point& r){
    return ((x-y)^(y-z))+((x-r)^(r-z));
}

ll cal(point& x, point& y, point& z){
    return (x-y)^(y-z);
}

ll inv(ll x){
    return power(x, mod-2);
}

void solve() {
    cin >> n;
    last[0].clear();
    for (int i = 1; i <= n; ++i){
        cin >> p[i].f;
        last[i] = last[i-1];
        last[i][p[i].f] = i;
    }
    fir[n+1].clear();
    for (int i = n; i >= 1; --i) {
        fir[i] = fir[i+1];
        fir[i][p[i].f] = i;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp2[i][j] = dp1[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;

    for (int i = 3; i <= n; ++i) {
        for (int j = 1; j <= n-i; ++j) {
            if (p[j].f == p[j+i].f){
                int mx = 0;
                for (int k = j+1; k <= j+i-1; ++k) {
                    if (last[j+i-1][p[k].f] >= max(mx, k+1)){
                        mx = last[j+i-1][p[k].f];
                        dp1[j][j+i] = max(dp1[k][mx]+ cal(p[j], p[j+i], p[mx], p[k]), dp1[j][j+i]);
                    }
                }
            }
        }
    }

    for (int i = n-3; i >= 1; --i) {
        for (int j = 1; j <= n-i; ++j) {
            if (p[j].f == p[j+i].f){
                int mx = 0, x;
                for (int k = j-1; k >= 1; --k) {
                    x = fir[j+i+1][p[k].f];
                    if (x > j+i){
                        dp2[j][j+i] = max(dp2[j][j+i], dp2[k][x]+ cal(p[k], p[x], p[j+i], p[j]));
                    }else{
                        x = fir[1][p[k].f];
                        if (x < k) dp2[j][j+i] = max(dp2[j][j+i], dp2[k][x]+cal(p[k], p[x], p[j+i], p[j]));
                    }
                }
                for (int k = n; k >= i+j+1; --k) {
                    x = fir[j+i+1][p[k].f];
                    if (x > j+i && x < k) dp2[j][j+i] = max(dp2[j][j+i], dp2[k][x]+ cal(p[k], p[x], p[j+i], p[j]));
                }
            }
        }
    }

    ll an = 0;
    int mx = 0;
    ll x;
//    for (int i = 1; i <= n; ++i) {
//        for (int j = mx; j <= n; ++j) {
//            if (p[i].f != p[j].f) continue;
//            an = max(an, dp1[i][j]);
//            for (int k = 1; k < i; ++k){
//                x = dp1[i][j]+ cal(p[i], p[j], p[k]);
//                if (an < x) mx = k, an = x;
//            }
//            for (int k = j+1; k <= n; ++k) {
//                x = dp1[i][j]+ cal(p[i], p[j], p[k]);
//                if (an < x) mx = k, an = x;
//            }
//        }
//    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i+1; j <= n; ++j) {
            if (p[i].f != p[j].f) continue;
            an = max(an, dp1[i][j]);
            for (int k = 1; k < i; ++k) an = max(an, dp1[i][j]+ cal(p[k], p[i], p[j]));
            for (int k = j+1; k <= n; ++k) an = max(an, dp1[i][j]+ cal(p[k], p[i], p[j]));
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i+1; j <= n; ++j) {
            if (p[i].f != p[j].f) continue;
            an = max(an, dp2[i][j]);
            for (int k = i+1; k < j; ++k) {
                an = max(an, dp2[i][j]+cal(p[i], p[j], p[k]));
            }
        }
    }
    cout << an << "\n";
}

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