#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define x first
#define y second
const int N=5e4+40;
vector<pii>g[N];
int a[N],pos[N];
int f[N];
int find(int x){
	if(x==f[x])	return x;
	return f[x]=find(f[x]);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			g[i].clear();
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			pos[a[i]]=i;
		}
		int d=sqrt(n-1);
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n&&(j-i)<=d;j++){
				ll val=abs(a[i]-a[j]);
				ll v=val*abs(j-i);
				if(v<=n-1){
					g[v].push_back({i,j});
				}
			}
			for(int j=a[i]+1;j<=n&&(j-a[i])<=d;j++){
				ll val=j-a[i];
				ll v=val*abs(pos[j]-i);
				if(v<=n-1){
					g[v].push_back({i,pos[j]});
				}
			}
		}
		for(int i=1;i<=n;i++){
			f[i]=i;
		}
		ll ans=0;
		//直接桶不用排序
		int sum=n-1;
		for(int i=1;i<=n-1;i++){
			for(int j=0;j<g[i].size();j++){
				auto a=g[i][j];
				int u=a.x,v=a.y;
				int c=find(u),d=find(v);
				if(c!=d){
					f[d]=c;
					ans+=i;
					sum--;
				}else {
					continue;
				}
			}
			if(!sum)	break;
		}
		printf("%lld\n",ans);
	}
	return 0;
}