#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a) {
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n') {
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL
	#undef gc
	#undef flush
}
using namespace FastIO;
const int N = 3e5 + 5,Lg = 20;
typedef long long ll;
int SubId,n;
int a[N],b[N],w[N];
int lg[N];

struct SA {
	SA(){}
	int v1[N],v2[N];
	int sa[N],ton[N];
	inline bool cmp(int *r,int i,int j,int k) { 
        return r[i] == r[j] && (i + k > n ? 0 : r[i + k]) == (j + k > n ? 0 : r[j + k]);
    }
	inline void Getsa(int *s,int *sa,int n,int m) {
		#define For(i,a,b) for(int i = (a);i <= (b);i++)
		#define Rof(i,a,b) for(int i = (a);i >= (b);i--)
		For(i,1,n) sa[i] = rk[i] = v1[i] = v2[i] = 0;
		int *x = v1,*y = v2,*t;
		For(i,0,m) ton[i] = 0;
		For(i,1,n) ton[x[i] = s[i]]++;
		For(i,0,m) ton[i] += ton[i - 1];
		Rof(i,n,1) sa[ton[x[i]]--] = i;
		for(int j = 1,p;j <= n;j *= 2,m = p) {
			p = 0;
			For(i,n - j + 1,n) y[++p] = i;
			For(i,1,n) if(sa[i] > j) y[++p] = sa[i] - j;
			For(i,0,m) ton[i] = 0;
			For(i,1,n) ton[x[y[i]]]++;
			For(i,1,m) ton[i] += ton[i - 1];
			Rof(i,n,1) sa[ton[x[y[i]]]--] = y[i],y[i] = 0;
			t = x;x = y;y = t;p = 1;x[sa[1]] = 1;
			For(i,2,n) 
				x[sa[i]] = cmp(y,sa[i - 1],sa[i],j) ? p : (++p);
			if(p >= n) break;
		}
		#undef For
		#undef Rof
	}
	int rk[N],height[N];
	inline void GetHeight(int *s,int n) {
		s[n + 1] = 0;
		for(int i = 1;i <= n;i++) rk[sa[i]] = i;
		for(int i = 1,j = 0;i <= n;i++) {
			if(j) --j;
			if(rk[i] != 1) 
				while(i + j <= n && sa[rk[i] - 1] + j <= n && s[i + j] == s[sa[rk[i] - 1] + j]) ++j;
			height[rk[i]] = j;
		}
	}
	int ST[Lg][N];
	inline int LCP(int l,int r) {
		if(l < 1 || r < 1 || l > n || r > n) return 0;
		l = rk[l];r = rk[r];
		if(l > r) swap(l,r);
        int t = __lg(r - (++l) + 1);
        return min(ST[t][l], ST[t][r - (1 << t) + 1]);
	}
	inline void init(int *a,int n) {
		for(int i = 1;i <= n;i++) rk[i] = sa[i] = height[i] = 0;
		Getsa(a,sa,n,n);
		GetHeight(a,n);
		for(int i = 1;i <= n;i++) ST[0][i] = height[i];
		for(int j = 1;j < Lg;j++)
			for(int i = 1;i + (1 << j) - 1 <= n;i++)
				ST[j][i] = min(ST[j - 1][i],ST[j - 1][i + (1 << j - 1)]);
	}
};
SA A,B;

struct BCJ {
	int fa[N],sze[N];
	inline void init(int n) { for(int i = 1;i <= n;i++) fa[i] = i,sze[i] = 1;}
	int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]);}
	inline void Merge(int x,int y) {
		x = find(x);y = find(y);
		if(x == y) return;
		if(sze[x] < sze[y]) swap(x,y);
		fa[y] = x;sze[x] += sze[y];
	}
	inline int Same(int x,int y) { return find(x) == find(y);}
}S[Lg],S0;

long long ans;
inline void Union(int x,int y,int dep) { // [x,x + 2^{dep}) , [y,y + 2^{dep})
	if(S[dep].Same(x,y)) return;
	if(dep == 0) {
		if(!S0.Same(x,y)) ans += w[y - x],S0.Merge(x,y);
		return;
	}
	S[dep].Merge(x,y);
	Union(x,y,dep - 1);
	if(y + (1 << dep - 1) <= n) Union(x + (1 << dep - 1),y + (1 << dep - 1),dep - 1);
}
int srt[N];
inline void Work() {
	read(n);
	for(int i = 1;i <= n;i++) read(a[i]),b[n - i + 1] = a[i];
	for(int i = 1;i <= n / 2;i++) read(w[i]),srt[i] = i;
	A.init(a,n);B.init(b,n);
	sort(srt + 1,srt + n / 2 + 1,[&](const int &x,const int &y) { return w[x] < w[y];});
	S0.init(n);
	for(int i = 0;i < Lg;i++) S[i].init(n);
	lg[0] = -1;
	for(int i = 1;i <= n;i++) lg[i] = lg[i >> 1] + 1;
	ans = 0;
	for(int _ = 1;_ <= n / 2;_++) {
		int len = srt[_];
		for(int i = len;i + len <= n;i += len) {
			int l = i,r = i + len;
			int L = n - (r - 1) + 1,R = n - (l - 1) + 1;
			int lcp = A.LCP(l,r);lcp = min(lcp,len);
			int lcs = B.LCP(L,R);lcs = min(lcs,len - 1);
			if(lcp + lcs >= len) {
				int tlen = lcp + lcs - len + 1;
				int cl = i - lcs,cr = cl + tlen - 1;
				cr = cr + len - 1;
				int k = lg[cr - cl + 1];
				Union(cl,cl + len,k);
				Union(cr - (1 << k) + 1,cr - (1 << k) + 1 + len,k);
			}
		}
	}
	write(ans);
}
int main() {
	// freopen("mst.in","r",stdin);
	// freopen("mst.out","w",stdout);
	int T;read(T);
	while(T--) Work();
	return 0;
}
/*
1
9
1 2 2 1 2 2 2 2 2
4 1 3 4
*/