#include <bits/stdc++.h>
using namespace std;
int dx[1005][1005];
int dy[1005][1005];
long long int dp[1005][1005];
int h[10005];
long long int f(int v[],int x,int y,int n,int level)
{
if(x < 1 || y > n) {
return LONG_MAX;
}
if(level == n) {
return n;
}
if(dp[x][y] != 0) {
return dp[x][y];
}
long long int left = f(v,min(x,y)-1,y,n,level+1) + ((long long)level*(long long)dx[x][y]);
//cout<<h[x]<<' '<<h[y]<<endl;
//cout<<level<<' '<<dx[x][y]<<endl;
long long int right = f(v,x,max(x,y)+1,n,level+1) + ((long long)level*(long long)dy[y][x]);
// cout<<x<<' '<<y<<endl;
// cout<<level<<' '<<left<<' '<<right<<endl;
dp[x][y] = min(left,right);
return dp[x][y];
}
int main()
{
int n;
int t;
int i;
long long int x;
long long int min;
int j;
int a[100005];
cin>>t;
while(t--) {
scanf("%d",&n);
//n = 1000;
memset(dp,0,sizeof(dp));
min = LONG_MAX;
for(i = 0; i < n; i++) {
scanf("%d",&a[i]);
h[a[i]] = i+1;
}
for(i = 1; i <= n; i++) {
dx[i][i] = h[i];
for(j = i+1; j <= n; j++) {
dx[i][j] = dx[i][j-1] - (h[i]>h[j]?1:0);
}
}
for(i = 1; i <= n; i++) {
dy[i][i] = h[i];
for(j = i-1; j >= 1; j--) {
dy[i][j] = dy[i][j+1] - (h[i]>h[j]?1:0);
}
}
for(i = 0; i < n; i++) {
x = f(a,a[i],a[i],n,1);
// cout<<x<<" ss"<<endl;
//cout<<"ss"<<endl;
if(x < min) {
min = x;
}
}
printf("%lld\n",min);
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBkeFsxMDA1XVsxMDA1XTsKaW50IGR5WzEwMDVdWzEwMDVdOwpsb25nIGxvbmcgaW50IGRwWzEwMDVdWzEwMDVdOwppbnQgaFsxMDAwNV07CmxvbmcgbG9uZyBpbnQgZihpbnQgdltdLGludCB4LGludCB5LGludCBuLGludCBsZXZlbCkKewoKICAgIGlmKHggPCAxIHx8IHkgPiBuKSB7CiAgICAgICAgcmV0dXJuIExPTkdfTUFYOwogICAgfQoKICAgIGlmKGxldmVsID09IG4pIHsKICAgICAgICByZXR1cm4gbjsKICAgIH0KICAgIGlmKGRwW3hdW3ldICE9IDApIHsKICAgICAgICByZXR1cm4gZHBbeF1beV07CiAgICB9CgogICAgIGxvbmcgbG9uZyBpbnQgbGVmdCA9IGYodixtaW4oeCx5KS0xLHksbixsZXZlbCsxKSArICgobG9uZyBsb25nKWxldmVsKihsb25nIGxvbmcpZHhbeF1beV0pOwogICAgLy9jb3V0PDxoW3hdPDwnICc8PGhbeV08PGVuZGw7CiAgICAvL2NvdXQ8PGxldmVsPDwnICc8PGR4W3hdW3ldPDxlbmRsOwogICAgIGxvbmcgbG9uZyBpbnQgcmlnaHQgPSBmKHYseCxtYXgoeCx5KSsxLG4sbGV2ZWwrMSkgKyAoKGxvbmcgbG9uZylsZXZlbCoobG9uZyBsb25nKWR5W3ldW3hdKTsKICAgLy8gY291dDw8eDw8JyAnPDx5PDxlbmRsOwogICAvLyBjb3V0PDxsZXZlbDw8JyAnPDxsZWZ0PDwnICc8PHJpZ2h0PDxlbmRsOwogICAgZHBbeF1beV0gPSAgbWluKGxlZnQscmlnaHQpOwogICAgcmV0dXJuIGRwW3hdW3ldOwoKCn0KaW50IG1haW4oKQp7CiAgICBpbnQgbjsKICAgIGludCB0OwogICAgaW50IGk7CiAgICBsb25nIGxvbmcgaW50IHg7CiAgICBsb25nIGxvbmcgaW50IG1pbjsKICAgIGludCBqOwogICAgaW50IGFbMTAwMDA1XTsKCgogICAgY2luPj50OwogICAgd2hpbGUodC0tKSB7CiAgICAgICAgc2NhbmYoIiVkIiwmbik7CiAgICAgICAgLy9uID0gMTAwMDsKICAgICAgICBtZW1zZXQoZHAsMCxzaXplb2YoZHApKTsKICAgICAgICBtaW4gPSBMT05HX01BWDsKICAgICAgICBmb3IoaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgc2NhbmYoIiVkIiwmYVtpXSk7CiAgICAgICAgICAgIGhbYVtpXV0gPSBpKzE7CiAgICAgICAgfQogICAgICAgIGZvcihpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgZHhbaV1baV0gPSBoW2ldOwogICAgICAgICAgICBmb3IoaiA9IGkrMTsgaiA8PSBuOyBqKyspIHsKICAgICAgICAgICAgICAgIGR4W2ldW2pdID0gZHhbaV1bai0xXSAtIChoW2ldPmhbal0/MTowKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBmb3IoaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgICAgIGR5W2ldW2ldID0gaFtpXTsKICAgICAgICAgICAgZm9yKGogPSBpLTE7IGogPj0gMTsgai0tKSB7CiAgICAgICAgICAgICAgICBkeVtpXVtqXSA9IGR5W2ldW2orMV0gLSAoaFtpXT5oW2pdPzE6MCk7CiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICAgICAgIGZvcihpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICAgICB4ID0gZihhLGFbaV0sYVtpXSxuLDEpOwogICAgICAgICAvLyAgIGNvdXQ8PHg8PCIgc3MiPDxlbmRsOwogICAgICAgICAgICAvL2NvdXQ8PCJzcyI8PGVuZGw7CiAgICAgICAgICAgIGlmKHggPCBtaW4pIHsKICAgICAgICAgICAgICAgIG1pbiA9IHg7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcHJpbnRmKCIlbGxkXG4iLG1pbik7CiAgICB9Cn0K