#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;

const int N = 200011;
struct basis {
  ull a[63], b[63];
  basis() { memset(a, 0, sizeof a), memset(b, 0, sizeof b); }
  void clear() { memset(a, 0, sizeof a), memset(b, 0, sizeof b); }
  void insert(ull x, ull y) {
    for (int k = 60; k >= 0; --k)
      if (x & (1ull << k)) {
        if (a[k]) {
          if (y > b[k]) swap(x, a[k]), swap(y, b[k]);
          x ^= a[k];
        } else {
          a[k] = x, b[k] = y;
          return;
        }
      }
  }
  ull query() {
    ull res = 0;
    for (int k = 60; k >= 0; --k) res += b[k];
    return res;
  }
  void see() {
    // for (int k = 60; k >= 0; --k)
    //   if (a[k]) log("A[%d]=%d;", k, a[k]);
    // log("\n");
  }
} bs[N];
vector<int> g[N];
int fa[20][N];
ull w[N];
struct SAM {
  int t[N][26], pre[N], len[N], val[N];
  int last, tot;
  SAM() { last = tot = 1; }
  void clear() {
    while (tot) bs[tot].clear(), g[tot].clear(), memset(t[tot], 0, sizeof t[tot]), val[tot] = pre[tot] = len[tot] = 0, --tot;
    last = tot = 1;
  }
  void extend(int w) {
    int pos = last, cur = ++tot;
    len[cur] = len[pos] + 1, last = cur;
    while (pos && !t[pos][w]) t[pos][w] = cur, pos = pre[pos];
    if (!pos) {
      pre[cur] = 1;
      return;
    }
    int nxt = t[pos][w];
    if (len[nxt] == len[pos] + 1) pre[cur] = nxt;
    else {
      int tmp = ++tot;
      len[tmp] = len[pos] + 1, memcpy(t[tmp], t[nxt], sizeof t[nxt]);
      pre[tmp] = pre[nxt], pre[cur] = pre[nxt] = tmp;
      while (pos && t[pos][w] == nxt) t[pos][w] = tmp, pos = pre[pos];
    }
  }
  void dfs1(int u) {
    for (auto v : g[u]) dfs1(v), val[u] += val[v];
  }
  void dfs2(int u) {
    bs[u].insert(w[val[u]], w[val[u]]);
    for (auto v : g[u]) {
      dfs2(v);
      for (int k = 0; k <= 60; ++k)
        if (bs[v].a[k]) bs[u].insert(bs[v].a[k], bs[v].b[k]);
    }
  }
  void build() {
    for (int i = 2; i <= tot; ++i) g[pre[i]].emplace_back(i), fa[0][i] = pre[i];
    for (int k = 1; k < 20; ++k)
      for (int u = 1; u <= tot; ++u) fa[k][u] = fa[k - 1][fa[k - 1][u]];
    dfs1(1), dfs2(1);
  }
} sam;
string s;
int ed[N];
int main() {
#ifdef memset0
  freopen("D.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  int task;
  cin >> task;
  while (task--) {
    sam.clear();
    int n, m;
    cin >> n >> s;
    s.insert(s.begin(), '!');
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= n; ++i) {
      sam.extend(s[i] - 'a');
      ed[i] = sam.last;
      ++sam.val[ed[i]];
    }
    sam.build();
    cin >> m;
    while (m--) {
      int l, r;
      cin >> l >> r;
      int u = ed[r];
      for (int k = 19; k >= 0; --k)
        if (fa[k][u] && sam.len[fa[k][u]] >= r - l + 1) u = fa[k][u];
      // log("u=%d,bs:", u), bs[u].see();
      cout << bs[u].query() << '\n';
    }
  }
  return 0;
}