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

const int MAXN = 300005;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PR;
#define fi first
#define se second
#define PB push_back
#define MP make_pair

ll C[MAXN];
char st[MAXN];
int id[MAXN];

ll A[125];
struct LBnode{ ll b[60], c[60]; ull sum = 0; } LB[MAXN];

void LBclear(int y) {
	for (int i = 0; i < 60 ; ++ i) LB[y].b[i] = LB[y].c[i] = 0; 
	LB[y].sum = 0;
}
void insert(int x, ll B) {
	ll C = B;
	for (int i = 59; i >= 0 ; -- i) {
		if (!(B >> i) & 1) continue;
		if (LB[x].b[i]) B ^= LB[x].b[i];
		else { LB[x].b[i] = B, LB[x].c[i] = C, LB[x].sum += C; break; }
	}
}
void merge(int x, int y) {
	int num = 0;
	for (int i = 0; i < 60 ; ++ i) if (LB[x].b[i]) A[++ num] = LB[x].c[i];
	for (int i = 0; i < 60 ; ++ i) if (LB[y].b[i]) A[++ num] = LB[y].c[i];
	sort(A + 1, A + num + 1);
	reverse(A + 1, A + num + 1);
	LBclear(y);
	for (int i = 1; i <= num ; ++ i) insert(y, A[i]);
}

int sz, lst, ch[MAXN][26], len[MAXN], fa[MAXN], a[MAXN], cnt[MAXN], num[MAXN], Fa[MAXN][20];
void Init() {
	memset(ch, 0, (sz + 10) * sizeof ch[0]);
	sz = 2, lst = 1;
}
void Insert(int c) {
	int p = lst, np = lst = sz ++;
	len[np] = len[p] + 1;
	for (; p && !ch[p][c] ; p = fa[p]) ch[p][c] = np;
	if (!p) { fa[np] = 1; return; }
	int q = ch[p][c];
	if (len[q] == len[p] + 1) fa[np] = q;
	else {
		int nq = sz ++;
		len[nq] = len[p] + 1;
		memcpy(ch[nq], ch[q], sizeof ch[0]);
		fa[nq] = fa[q];
		fa[np] = fa[q] = nq;
		for (; p && ch[p][c] == q ; p = fa[p]) ch[p][c] = nq;
	}
}
void Build() {
	for (int i = 1; i < sz ; ++ i) cnt[i] = 0;
	for (int i = 1; i < sz ; ++ i) cnt[len[i]] ++;
	for (int i = 1; i < sz ; ++ i) cnt[i] += cnt[i - 1];
	for (int i = sz - 1; i >= 1 ; -- i) a[cnt[len[i]] --] = i;	
	for (int i = sz - 1; i >= 1 ; -- i) num[fa[a[i]]] += num[a[i]];

	for (int i = sz - 1; i >= 2 ; -- i) insert(a[i], C[num[a[i]]]);
	for (int i = sz - 1; i >= 2 ; -- i) merge(a[i], fa[a[i]]);

	for (int i = 2; i < sz ; ++ i) Fa[i][0] = fa[i];
	for (int i = 2; i < sz ; ++ i)
		for (int j = 1; j < 20 ; ++ j)
			Fa[a[i]][j] = Fa[Fa[a[i]][j - 1]][j - 1];
}
signed main() {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif
	int Case;
	scanf("%d", &Case);
	while (Case --) {
		for (int i = 1; i < sz ; ++ i) LBclear(i), id[i] = num[i] = 0;
		Init();

		int n;
		scanf("%d", &n);
		scanf("%s", st + 1);
		for (int i = 1; i <= n ; ++ i) Insert(st[i] - 'a'), id[i] = lst, ++ num[lst];
		for (int i = 1; i <= n ; ++ i) scanf("%lld", &C[i]);
		Build();
		int m;
		scanf("%d", &m);
		while (m --) {
			int l, r;
			scanf("%d%d", &l, &r);
			int nw = id[r];
			for (int j = 19; j >= 0 ; -- j)
				if (len[Fa[nw][j]] >= r - l + 1) nw = Fa[nw][j];
			printf("%llu\n", LB[nw].sum);
		}
	}
	return 0;
}