#include<bits/stdc++.h>
using namespace std;
string O="()[]{}<>";
const int N=5e5+10,mod=1e9+9,mod2=1e9+7,PP=1e6;
mt19937 rnd(time(0));
int W=rnd()%PP+PP,W2=rnd()%PP+PP;
int qpow(int a,int b,int mo){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mo;
        a=1ll*a*a%mo;
    }
    return c;
}
const int W_=qpow(W,mod-2,mod),W2_=qpow(W2,mod2-2,mod2);
char c[N];
int n,q,a[N],L[N],R[N];
int typ[N];
struct qq{
    int le,z,z2;
};
int WI[N],WI2[N],IW[N],IW2[N];
qq operator + (const qq &a,const qq &b){
    return (qq){a.le+b.le,
    (int)((1ll*a.z*WI[b.le]+b.z)%mod),
    (int)((1ll*a.z2*WI2[b.le]+b.z2)%mod2)};
}
qq operator - (const qq &a,const qq &b){
    return (qq){a.le-b.le,
    (int)(1ll*(a.z+mod-b.z)*IW[b.le]%mod),
    (int)(1ll*(a.z2+mod2-b.z2)*IW2[b.le]%mod2),
    };
}
bool operator == (const qq &a,const qq &b){
    return a.z==b.z&&a.z2==b.z2&&a.le==b.le;
}
qq ans[N];
vector<int>k[N<<2];
#define pb push_back
int wh[N];
void build(int p,int l,int r){
    k[p].clear();
    if(l==r){wh[l]=p;return;}int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
int lca(int x,int y){
    while(x!=y){if(x>y)x>>=1;else y>>=1;}
    return x;
}
int stt;
qq Hs(int x){return (qq){1,x/2+1,x/2+1};}
int db;
qq hp[N],ht[N],hp2[N],tt[N];int lo[N],sta[N];bool isi[N];
void sol(int p,int l,int r){
    if(l==r){
        for(int z:k[p])if(!(a[l]&1)){typ[z]=stt,ans[z]=Hs(a[l]);}
        return;
    }
    int mid=(l+r)>>1;
    sol(p<<1,l,mid),sol(p<<1|1,mid+1,r);
    for(int i=mid,t=0,top=0,fuc=0;i>=l;i--){
        if(fuc){isi[i]=0;continue;}
        if(!(a[i]&1)){
            if(top){
                if(sta[top]!=a[i]/2)fuc=1;
                else top--;
            }
            else{
                t++,hp[t]=Hs(a[i])+hp[t-1];
            }
        }
        else sta[++top]=a[i]/2;
        if(fuc){isi[i]=0;continue;}
        if(top)isi[i]=0;
        else isi[i]=1,lo[i]=t;
    }
    for(int i=mid+1,t=0,top=0,fuc=0;i<=r;i++){
        if(fuc){isi[i]=0;continue;}
        if(a[i]&1){
            if(top){
                if(sta[top]!=a[i]/2)fuc=1;
                else top--;
            }
            else{
                t++,hp2[t]=Hs(a[i])+hp2[t-1];
            }
        }
        else sta[++top]=a[i]/2,ht[top]=ht[top-1]+Hs(a[i]);
        if(fuc){isi[i]=0;continue;}
        lo[i]=t,isi[i]=1,tt[i]=ht[top];
    }
    for(int z:k[p]){
        if(!isi[L[z]]||!isi[R[z]])continue;
        if(lo[L[z]]>=lo[R[z]]&&hp[lo[R[z]]]==hp2[lo[R[z]]]){
            if(!tt[R[z]].le&&lo[L[z]]==lo[R[z]]){db++;continue;}
            typ[z]=stt,ans[z]=(hp[lo[L[z]]]-hp[lo[R[z]]])+tt[R[z]];
        }
    }
}
void doi(){
    build(1,1,n);
    for(int i=1;i<=q;i++)k[lca(wh[L[i]],wh[R[i]])].pb(i);
    sol(1,1,n);
}
#define pi pair<int,int>
map<pair<int,int>,int>di;
void sol(){
    db=0,di.clear();
    WI[0]=IW[0]=1;
    WI2[0]=IW2[0]=1;
    scanf("%d%d%s",&n,&q,c+1);
    for(int i=1;i<=n;i++)WI[i]=1ll*WI[i-1]*W%mod,IW[i]=1ll*IW[i-1]*W_%mod,
WI2[i]=1ll*WI2[i-1]*W2%mod2,IW2[i]=1ll*IW2[i-1]*W2_%mod2;
    for(int i=1;i<=n;i++){for(int j=0;j<8;j++)if(O[j]==c[i])a[i]=j;}
    for(int i=1;i<=q;i++)scanf("%d%d",&L[i],&R[i]),typ[i]=0;
    stt=1,doi();reverse(a+1,a+n+1);
    for(int i=1;i<=n;i++)a[i]^=1;
    for(int i=1;i<=q;i++)swap(L[i],R[i]),L[i]=n-L[i]+1,R[i]=n-R[i]+1;
    stt=2,doi();
    for(int i=1;i<=q;i++)if(typ[i]==1)di[{ans[i].z,ans[i].z2}]++;
    int sum=db/4;
    for(int i=1;i<=q;i++)if(typ[i]==2&&di[{ans[i].z,ans[i].z2}]>0)sum++,di[{ans[i].z,ans[i].z2}]--;
    printf("%d\n",sum);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}