#include<bits/stdc++.h>
#define N 400005
#define re 
#define ll unsigned long long
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
    re char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}
inline void Rd(ll &res){
    re char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}
char c[N];
ll a[N];
int fa[N][20],cnt[N];
int tot;
struct LBase{
    ll p[62],sum;
    ll a[62];
    int tot;
    int add(ll v){
        if(v==0)return 0;
        ll res=v;
        for(int i=60;i>=0;i--)if(v>>i&1){
            if(!p[i]){p[i]=v;sum+=res;a[++tot]=res;return 1;}
            v^=p[i];
        }

        return 0;
    }
    void clear(){
        memset(p,0,sizeof(p));sum=0;
        memset(a,0,sizeof(a));tot=0;
    }
}L[N];
inline LBase Merge(LBase A,LBase B){
    LBase C; C.clear();
    int t1=1,t2=1;
    while(t1<=A.tot&&t2<=B.tot){
        if(A.a[t1]>B.a[t2])C.add(A.a[t1]),t1++;
        else C.add(B.a[t2]),t2++;
    }
    while(t1<=A.tot)C.add(A.a[t1]),t1++;
    while(t2<=B.tot)C.add(B.a[t2]),t2++;
    return C;

}
int pos0,g[N],deg[N];
int Q[N];
struct SAM{
    int n,maxlen[N<<1],trans[N<<1][26],slink[N<<1],u;
    void clear(){
        memset(trans[0],0,sizeof(trans[0]));
        slink[0]=-1;
        n=0;u=0;
    }
    void add(char ch){
        int z=++n,c=ch-'a';
        maxlen[z]=maxlen[u]+1;
        pos0++;
        cnt[z]=1;
        g[pos0]=z;
        memset(trans[z],0,sizeof(trans[z]));
        while(u!=-1&&!trans[u][c])trans[u][c]=z,u=slink[u];
        if(u==-1){slink[z]=0;u=z;return;}
        int x=trans[u][c];
        if(maxlen[u]+1==maxlen[x]){slink[z]=x;u=z;return;}
        int y=++n;maxlen[y]=maxlen[u]+1;
        slink[y]=slink[x];
        for(re int i=0;i<26;i++)trans[y][i]=trans[x][i];
        slink[x]=y;slink[z]=y;
        while(u!=-1&&trans[u][c]==x)trans[u][c]=y,u=slink[u];
        u=z;
    }
    void Build(){
        for(int i=1;i<=n;i++){
            // adde(slink[i],i);
            deg[slink[i]]++;
            fa[i][0]=slink[i];
        }
        fa[0][0]=-1;
        int l=0,r=0;
        for(int i=0;i<=n;i++)
            if(deg[i]==0)Q[++r]=i;
        // puts("333");
        // dfs(0,-1);
        while(l<r){
            int x=Q[++l];
            int f=slink[x];
            // printf("%d %llu\n",x,a[cnt[x]]);
            // L[x].add(a[cnt[x]]);
            LBase res;res.clear();
            res.add(a[cnt[x]]);
            L[x]=Merge(L[x],res);
            L[f]=Merge(L[f],L[x]);
            cnt[f]+=cnt[x];
            deg[f]--;
            if(deg[f]==0)Q[++r]=f;
        }

        // for(int i=1;i<=n;i++){
        //     printf("now:%d %llu\n",i,L[i].sum);
        // }

        // puts("444");
        for(int i=1;i<=19;i++)
            for(int j=0;j<=n;j++)
                if(fa[j][i-1]!=-1)fa[j][i]=fa[fa[j][i-1]][i-1];
                else fa[j][i]=-1;
        // puts("555");
    }
}S;

int Up(int x,int len){
    for(int i=19;i>=0;i--)if(fa[x][i]!=-1){
        int f=fa[x][i];
        if(S.maxlen[f]>=len)x=f;
    }
    return x;
}
void Clear(){
    for(int i=0;i<=tot;i++)g[i]=0;

    for(int i=0;i<=tot;i++)deg[i]=0;

    for(int i=0;i<=tot;i++)
        for(int j=0;j<=19;j++)fa[i][j]=0;
    for(int i=0;i<=tot;i++)cnt[i]=0;
    for(int i=0;i<=tot;i++)L[i].clear();
    for(int i=0;i<=tot;i++){
        memset(S.trans[i],0,sizeof(S.trans[i]));
        S.slink[i]=0;
        S.maxlen[i]=0;
    }
    tot=0;pos0=0;
}
int main(){
    Rd(T);
    while(T--){
        Rd(n);
        scanf("%s",c+1);
        // for(int i=1;i<=n;i++)c[i]='a';
        S.clear();
        for(int i=1;i<=n;i++)S.add(c[i]);
        for(re int i=1;i<=n;i++)Rd(a[i]);
        // for(int i=1;i<=n;i++)a[i]=i;

        // puts("111");
        
        S.Build();
        tot=S.n;
        // puts("222");
        Rd(q);
        while(q--){
            int l,r;
            Rd(l),Rd(r);
            int x=g[r];
            x=Up(x,r-l+1);
            printf("%llu\n",L[x].sum);


        }




        Clear();
    }
    return 0;
}