#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <random>
#include <stdio.h>
#include <fstream>
#include <functional>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <chrono>


using namespace std;


#define rep(i,n) for (int i=0;i<n;i+=1)
#define rrep(i,n) for (int i=n-1;i>-1;i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n";

template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T>
using vvvec = vec<vvec<T>>;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;


template<class T>
bool chmin(T &a, T b){
  if (a>b){
    a = b;
    return true;
  }
  return false;
}

template<class T>
bool chmax(T &a, T b){
  if (a<b){
    a = b;
    return true;
  }
  return false;
}

template<class T>
T sum(vec<T> x){
  T res=0;
  for (auto e:x){
    res += e;
  }
  return res;
}

template<class T>
void printv(vec<T> x){
  for (auto e:x){
    cout<<e<<" ";
  }
  cout<<endl;
}



template<class T,class U>
ostream& operator<<(ostream& os, const pair<T,U>& A){
  os << "(" << A.first <<", " << A.second << ")";
  return os;
}

template<class T>
ostream& operator<<(ostream& os, const set<T>& S){
  os << "set{";
  for (auto a:S){
    os << a;
    auto it = S.find(a);
    it++;
    if (it!=S.end()){
      os << ", ";
    }
  }
  os << "}";
  return os;
}

template<class T0,class T1,class T2>
ostream& operator<<(ostream& os, const tuple<T0,T1,T2>& a){
  auto [x,y,z] = a;
  os << "(" << x << ", " << y << ", " << z << ")";
  return os;
}

template<class T>
ostream& operator<<(ostream& os, const map<ll,T>& A){
  os << "map{";
  for (auto e:A){
    os << e.first;
    os << ":";
    os << e.second;
    os << ", ";
  }
  os << "}";
  return os;
}

template<class T>
ostream& operator<<(ostream& os, const vec<T>& A){
  os << "[";
  rep(i,A.size()){
    os << A[i];
    if (i!=A.size()-1){
      os << ", ";
    }
  }
  os << "]" ;
  return os;
}



void solve(){
  int N;
  cin>>N;

  vec<int> A(N);
  rep(i,N) cin>>A[i];

  map<int,int> comp_A;
  rep(i,N) comp_A[A[i]] = 0;
  {
    int t = 0;
    for (auto a:comp_A){
      comp_A[a.first] = t++;
    }
    rep(i,N){
      A[i] = comp_A[A[i]];
    }
  }

  vec<pll> xy(N);
  rep(i,N){
    ll x,y;
    cin>>x>>y;
    xy[i] = {x,y};
  }

  rep(i,N){
    A.push_back(A[i]);
  }
  rep(i,N){
    xy.push_back(xy[i]);
  }
  N *= 2;

  vec<int> pre_idx(N,-1),nxt_idx(N,N);
  vec<vec<int>> val_to_preidx(N,vec<int>(N,-1)),val_to_nxtidx(N,vec<int>(N,N));

  vec<int> pre_memo(N,-1);
  rep(i,N){
    pre_idx[i] = pre_memo[A[i]];
    pre_memo[A[i]] = i;
    rep(j,N){
      val_to_preidx[i][j] = pre_memo[j];
    }
  }

  vec<int> nxt_memo(N,N);
  for (int i=N-1;0<=i;i--){
    nxt_idx[i] = nxt_memo[A[i]];
    nxt_memo[A[i]] = i;
    rep(j,N){
      val_to_nxtidx[i][j] = nxt_memo[j];
    }
  }

  auto get_triangle_area = [&](int i,int j,int k)->ll {
    ll a = xy[j].first - xy[i].first;
    ll b = xy[j].second - xy[i].second;
    ll c = xy[k].first - xy[i].first;
    ll d = xy[k].second - xy[i].second;
    return abs(a*d-b*c);
  };



  vec<vec<ll>> dp(N,vec<ll>(N,0));

  vec<int> tmp_done(N,0);

  for (int range_len = 1; range_len < N/2; range_len++){
    for (int l = 1; l < N-range_len; l++){
      int r = l + range_len - 1;

      if (A[l]!=A[r]) continue;

      for (int pl = l-1; 0 <= pl; pl--){
        if (tmp_done[A[pl]]) continue;
        tmp_done[A[pl]] = 1;
        for (int pr = val_to_nxtidx[r+1][A[pl]]; pr < min(N,pl+(N/2)-1); pr = nxt_idx[pr]){
          chmax(dp[pl][pr],dp[l][r] + get_triangle_area(pl,l,r) + get_triangle_area(pl,r,pr));
        }
      }
      for (int pl = l-1; 0 <= pl; pl--){
        tmp_done[A[pl]] = 0;
      }

      for (int pr = r + 1; pr < N; pr++){
        if (tmp_done[A[pr]]) continue;
        tmp_done[A[pr]] = 1;
        for (int pl = val_to_preidx[l-1][A[pr]]; max(0,pr-(N/2)+1) <= pl; pl = pre_idx[pl]){
          chmax(dp[pl][pr],dp[l][r] + get_triangle_area(pl,l,r) + get_triangle_area(pl,r,pr));
        }
      }
      for (int pr = r + 1; pr < N; pr++){
        tmp_done[A[pr]] = 0;
      }

    }
  }

  

  ll res = 0;
  rep(l,N){
    rep(r,N){
      if (r-l+1 <= (N/2)){
        chmax(res,dp[l][r]);
      }
    }
  }

  cout << res << endl;


  

  
  




}


int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int T;
  cin>>T;
  while (T--){
    solve();
  }
}