#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=3e5+5;
const int LG=19;

int n,a[N],Lg[N];
struct SA{
	int sa[N],rk[N],oldrk[N<<1],cnt[N],id[N],key1[N],h[N];
	int ST[LG][N],sz;
	bool cmp(int x,int y,int w){
		return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
	}
	void build(int a[],int n){
		int m=n,p=0;sz=n;
		for(int i=1;i<=n;i++)rk[i]=a[i],++cnt[rk[i]];
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
		for(int w=1;;w<<=1,m=p){
			p=0;
			for(int i=n;i>n-w;i--)id[++p]=i;
			for(int i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;
			memset(cnt,0,sizeof(cnt));
			for(int i=1;i<=n;i++)++cnt[key1[i]=rk[id[i]]];
			for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
			for(int i=n;i>=1;i--)sa[cnt[key1[i]]--]=id[i];
			memcpy(oldrk,rk,sizeof(oldrk));p=0;
			for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
			if(p==n){
				for(int i=1;i<=n;i++)sa[rk[i]]=i;
				break;
			}
		}
		for(int i=1,k=0;i<=n;i++){
			if(k>0)k--;
			while(a[i+k]==a[sa[rk[i]-1]+k])++k;
			h[rk[i]-1]=k;
		}

		// cout<<"a = ";for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts("");
		// cout<<"sa = ";for(int i=1;i<=n;i++)cout<<sa[i]<<" ";puts("");
		// cout<<"rk = ";for(int i=1;i<=n;i++)cout<<rk[i]<<" ";puts("");
		// cout<<"h = ";for(int i=1;i<=n;i++)cout<<h[i]<<" ";puts("");
		
		for(int i=1;i<n;i++)ST[0][i]=h[i];
		for(int i=1;i<LG;i++){
			for(int j=1;j+(1<<i)-1<n;j++){
				ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
			}
		}
	}
	int LCP(int i,int j){
		if(i==j)return n-i+1;
		int l=rk[i],r=rk[j];if(l>r)swap(l,r);r--;
		int k=Lg[r-l+1];
		return min(ST[k][l],ST[k][r-(1<<k)+1]);
	}

	void clear(){
		for(int i=1;i<=sz;i++)sa[i]=rk[i]=oldrk[i]=oldrk[i+sz]=cnt[i]=id[i]=key1[i]=h[i]=0;
		for(int i=0;i<LG;i++)for(int j=1;j<=sz;j++)ST[i][j]=0;
	}
}A,revA;

struct dsu{
	int fa[N],sz[N];
	void init(int n){for(int i=1;i<=n;i++)sz[i]=1,fa[i]=i;}
	int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
	void Link(int x,int y){
		x=find(x),y=find(y);
		if(sz[x]>sz[y])swap(x,y);
		fa[x]=y,sz[y]+=sz[x];
	}
}D[LG];

pair<int,int>w[N];
int val[N];ll ans=0;
void Merge(int i,int j,int p){
	// cout<<"Merge "<<i<<" "<<j<<" "<<p<<endl;
	if(D[p].find(i)==D[p].find(j))return ;
	D[p].Link(i,j);
	if(p==0)return ans+=val[j-i],void();
	Merge(i,j,p-1),Merge(i+(1<<(p-1)),j+(1<<(p-1)),p-1);
}

void solve(){
	n=read();int m=(int)(n/2);ans=0;
	for(int i=2;i<=n;i++)Lg[i]=Lg[i>>1]+1;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++)val[i]=w[i].fi=read(),w[i].se=i;
	for(int i=0;i<Lg[n];i++)D[i].init(n);

	A.build(a,n),reverse(a+1,a+n+1);
	revA.build(a,n),reverse(a+1,a+n+1);
	sort(w+1,w+m+1);

	for(int i=1;i<=m;i++){
		int k=w[i].se;
		// cout<<"k = "<<k<<endl;
		for(int j=k;j<=n-k;j+=k){
			if(a[j]!=a[j+k])continue;
			int L=revA.LCP(n-j+1,n-(j+k)+1),R=A.LCP(j,j+k);
			if(L+R-1<k)continue;
			L=j-L+1,R=j+R-1;int r=Lg[R-L+1];
			// cout<<"find a["<<L<<","<<R<<"] = a["<<L+k<<","<<R+k<<"]\n";
			Merge(L,L+k,r),Merge(R-(1<<r)+1,R+k-(1<<r)+1,r);
		}
	}

	cout<<ans<<endl;

	for(int i=1;i<=n;i++)val[i]=0,w[i]=mk(0,0);
	A.clear(),revA.clear();
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	int tt=read();while(tt--)solve();

	return 0;
}