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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; L++)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else 
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

const int maxn = 100025;

namespace sfx {

bool _t[maxn * 2];
int hi[maxn], rev[maxn];
int _s[maxn * 2], sa[maxn * 2], _c[maxn * 2];
int x[maxn], _p[maxn], _q[maxn * 2];

void pre(int *a, int *c, int n, int z) {
    memset(a, 0, sizeof(int) * n);
    memcpy(x, c, sizeof(int) * z);
}

void induce(int *a, int *c, int *s, bool *t, int n, int z) {
    memcpy(x + 1, c, sizeof(int) * (z - 1));
    for (int i = 0; i < n; ++i)
        if (a[i] && !t[a[i] - 1])
            a[x[s[a[i] - 1]]++] = a[i] - 1;
    memcpy(x, c, sizeof(int) * z);
    for (int i = n - 1; i >= 0; --i)
        if (a[i] && t[a[i] - 1])
            a[--x[s[a[i] - 1]]] = a[i] - 1;
}
void sais(int *s, int *a, int *p, int *q, bool *t, int *c, int n, int z) {
    bool uniq = t[n - 1] = true;
    int nn = 0, nmxz = -1, *nsa = a + n, *ns = s + n, last = -1;
    memset(c, 0, sizeof(int) * z);
    for (int i = 0; i < n; ++i)
        uniq &= ++c[s[i]] < 2;
    for (int i = 0; i < z - 1; ++i)
        c[i + 1] += c[i];
    if (uniq) {
        for (int i = 0; i < n; ++i)
            a[--c[s[i]]] = i;
        return;
    }
    for (int i = n - 2; i >= 0; --i)
        t[i] = (s[i] == s[i + 1] ? t[i + 1] : s[i] < s[i + 1]);
    pre(a, c, n, z);
    for (int i = 1; i <= n - 1; ++i)
        if (t[i] && !t[i - 1])
            a[--x[s[i]]] = p[q[i] = nn++] = i;
    induce(a, c, s, t, n, z);
    for (int i = 0; i < n; ++i) {
        if (a[i] && t[a[i]] && !t[a[i] - 1]) {
            bool neq = last < 0 || \
                       memcmp(s + a[i], s + last, (p[q[a[i]] + 1] - a[i]) * sizeof(int));
            ns[q[last = a[i]]] = nmxz += neq;
        }
    }
    sais(ns, nsa, p + nn, q + n, t + n, c + z, nn, nmxz + 1);
    pre(a, c, n, z);
    for (int i = nn - 1; i >= 0; --i)
        a[--x[s[p[nsa[i]]]]] = p[nsa[i]];
    induce(a, c, s, t, n, z);
}
void build(const string &s) {
    const int n = int(s.size());
    for (int i = 0; i < n; ++i) _s[i] = s[i];
    _s[n] = 0;
    sais(_s, sa, _p, _q, _t, _c, n + 1, 256);
    for (int i = 0; i < n; ++i)
        rev[sa[i] = sa[i + 1]] = i;
    int ind = hi[0] = 0;
    for (int i = 0; i < n; ++i) {
        if (!rev[i]) {
            ind = 0;
            continue;
        }
        while (i + ind < n && \
                s[i + ind] == s[sa[rev[i] - 1] + ind])
            ++ind;
        hi[rev[i]] = ind ? ind-- : 0;
    }
}

}

struct Dsu {
    vector<int> pa, sz;
    vector<vector<uint64_t>> bas;
    vector<uint64_t> sum;

    Dsu(int n) : pa(n), sz(n, 1), bas(n), sum(n) {
        iota(pa.begin(), pa.end(), 0);
    }
    int anc(int x) {
        return x==pa[x] ? x : pa[x]=anc(pa[x]);
    }
    void join(int x, int y) {
        x = anc(x);
        y = anc(y);
        assert (x != y);

        if (sz[x] < sz[y]) swap(x, y);
        vector<uint64_t> tmp(bas[x].size() + bas[y].size()), b;
        merge(all(bas[x]), all(bas[y]), tmp.begin(), greater<>());
        bas[x].clear(), bas[y].clear();
        uint64_t tmpsum = 0;
        for (uint64_t z: tmp) {
            uint64_t orz = z;
            for (uint64_t w: b) {
                z = min(z, w ^ z);
                if (!z) break;
            }
            if (z) {
                b.push_back(z);
                bas[x].push_back(orz);
                tmpsum += orz;
            }
        }

        pa[y] = x;
        sz[x] += sz[y];
        sum[x] = tmpsum;
    }

    void insert(int p, uint64_t x) {
        p = anc(p);
        vector<uint64_t> b, tmp;
        tmp.swap(bas[p]);
        tmp.push_back(x);
        sort(tmp.begin(), tmp.end(), greater<>());
        uint64_t tmpsum = 0;
        for (uint64_t z: tmp) {
            uint64_t orz = z;
            for (uint64_t w: b) {
                z = min(z, w ^ z);
                if (!z) break;
            }
            if (z) {
                b.push_back(z);
                bas[p].push_back(orz);
                tmpsum += orz;
            }
        }
        sum[p] = tmpsum;
    }

    int getSize(int x) {
        return sz[anc(x)];
    }

    uint64_t getSum(int x) {
        return sum[anc(x)];
    }

};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        vector<uint64_t> W(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> W[i];

        Dsu dsu(n);

        sfx::build(s);
        vector<tuple<int,int,int>> evt;
        for (int i = 1; i < n; i++) {
            evt.emplace_back(sfx::hi[i], -1, i);
        }

        int m;
        cin >> m;
        vector<uint64_t> ans(m);
        for (int i = 0; i < m; i++) {
            int l, r;
            cin >> l >> r;
            tie(l, r) = make_pair(n - r, n - l + 1);

            int len = r - l;
            evt.emplace_back(len, i, sfx::rev[l]);
        }

        for (int i = 0; i < n; i++) {
            debug(i, sfx::hi[i], s.substr(sfx::sa[i]));
        }


        for (int i = 0; i < n; i++)
            dsu.insert(i, W[1]);

        sort(evt.begin(), evt.end(), greater<>());

        for (size_t i = 0, j; i < evt.size(); i = j) {
            for (j = i; j < evt.size(); j++) {
                if (get<0>(evt[i]) != get<0>(evt[j]))
                    break;
            }
            for (size_t t = i; t < j; t++) {
                auto [h, qid, pos] = evt[t];
                if (qid < 0) {
                    debug("JOIN", pos - 1, pos);
                    dsu.join(pos - 1, pos);
                }
            }

            for (size_t t = i; t < j; t++) {
                auto [h, qid, pos] = evt[t];
                if (qid < 0) {
                    dsu.insert(pos, W[dsu.getSize(pos)]);
                }
            }

            for (size_t t = i; t < j; t++) {
                auto [h, qid, pos] = evt[t];
                if (qid >= 0) {
                    // query
                    ans[qid] = dsu.getSum(pos);
                }
            }

        }

        for (int i = 0; i < m; i++) {
            cout << ans[i] << '\n';
        }
    }

    return 0;
}