#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 2e5 + 10, M = N * 2;

int head[N], ver[M], nxt[M], tot = 1;
void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

int n, m;
int sz[N], pos[N], fa[N][25];
ull a[N]; 
char s[N];

struct LinearBasis {
    ull a[65], b[65];
    LinearBasis() { memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b)); }
    void init() { memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b)); }
    void insert(ull x, ull y) {
        for (int i = 60; ~i; i--) {
            if (x >> i & 1) {
                if (a[i]) {
                    if (y > b[i]) swap(x, a[i]), swap(y, b[i]);
                    x ^= a[i];
                } else {
                    a[i] = x, b[i] = y;
                    break;
                }
            }
        }
    }
    ull ask() {
        ull ans = 0;
        for (int i = 0; i <= 60; i++) ans += b[i];
        return ans;
    }
} L[N];

void merge(LinearBasis& x, LinearBasis& y) {
    for (int i = 0; i <= 60; i++)
        if (y.a[i]) x.insert(y.a[i], y.b[i]);
}

struct SAM {
    int len, fa, c[30];
    SAM (int len = 0, int fa = 0) : len(len), fa(fa) { memset(c, 0, sizeof(c)); }
} t[N];

int last = 1, idx = 1;

void insert(int id, int k) {
    int x = ++idx, p = last;
    t[x] = SAM(t[p].len + 1, 0);
    for (; !t[p].c[k]; p = t[p].fa) t[p].c[k] = x;
    if (!p) t[x].fa = 1;
    else {
        int q = t[p].c[k];
        if (t[q].len == t[p].len + 1) t[x].fa = q;
        else {
            int nq = ++idx;
            t[nq] = t[q], t[nq].len = t[p].len + 1;
            for (; p && t[p].c[k] == q; p = t[p].fa) t[p].c[k] = nq;
            t[x].fa = t[q].fa = nq;
        }
    }
    last = x;
    sz[x]++, pos[id] = x;
}

void dfs1(int x) {
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        dfs1(y);
        sz[x] += sz[y];
    }
}

void dfs2(int x) {
    L[x].insert(a[sz[x]], a[sz[x]]);
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        dfs2(y);
        merge(L[x], L[y]);
    }
}

void clear() {
    for (int i = 0; i <= idx; i++) head[i] = sz[i] = 0, t[i] = SAM();
    last = idx = 1, tot = 1;
}

void solve() {
    clear();
    cin >> n >> s + 1;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) insert(i, s[i] - 'a');
    for (int i = 2; i <= idx; i++) add(t[i].fa, i);
    for (int i = 1; i <= idx; i++) fa[i][0] = t[i].fa;
    for (int k = 1; k < 20; k++)
        for (int i = 1; i <= idx; i++) fa[i][k] = fa[fa[i][k - 1]][k - 1];
    dfs1(1), dfs2(1);
    cin >> m;
    while (m--) {
        int l, r; cin >> l >> r;
        int x = pos[r];
        for (int k = 19; ~k; k--)
            if (t[fa[x][k]].len >= r - l + 1) x = fa[x][k];
            cout << L[x].ask() << endl;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}