#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5;
const int mod=998244353;
int ksm(ll x,int tp,int s=1){
    for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
    return s;
}
mt19937 rnd(1293421);
struct Mt{
    int a[2][2];
    bool operator < (const Mt x) const{
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++){
                if(a[i][j]<x.a[i][j]) return 1;
                if(a[i][j]>x.a[i][j]) return 0;
            }
        return 0;
    }
    Mt(){ memset(a,0,sizeof a); }
    int det(){ return ((1ll*a[0][0]*a[1][1]-1ll*a[0][1]*a[1][0])%mod+mod)%mod; }
    void gen(){
        while(1){
            for(int i=0;i<2;i++){
                a[i][0]=rnd()%mod;
                a[i][1]=rnd()%mod;
            }
            if(det())
                break;
        }
    }
    Mt geniv(){
        Mt iv;
        int dv=ksm(det(),mod-2);
        iv.a[0][0]=a[1][1];
        iv.a[1][0]=mod-a[1][0];
        iv.a[0][1]=mod-a[0][1];
        iv.a[1][1]=a[0][0];
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                iv.a[i][j]=1ll*iv.a[i][j]*dv%mod;
        return iv;
    }
}I;
Mt operator * (const Mt x,const Mt y){
    Mt z;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            z.a[i][j]=(1ll*x.a[i][0]*y.a[0][j]+1ll*x.a[i][1]*y.a[1][j])%mod;
    return z;
}
Mt v[5],iv[5];
void prep(){
    I.a[0][0]=I.a[1][1]=1;
    for(int i=1;i<=4;i++){
        v[i].gen();
        iv[i]=v[i].geniv();
    }
}
int n,m;
char s[N+5];
Mt vals[N+5];
int gid(char c){
    switch(c){
    case '(': return 1;
    case ')': return -1;
    case '[': return 2;
    case ']': return -2;
    case '{': return 3;
    case '}': return -3;
    case '<': return 4;
    case '>': return -4;
    default:
        assert(0);
    }
}
struct oper{
    int l,r;
}a[N+5];
Mt va[N+5];
bool okl[N+5],okr[N+5];
int mn[20][N+5];
map<Mt,int> cnt;
int qmn(int l,int r){
    int k=(int)log2(r-l+1);
    return min(mn[k][l],mn[k][r-(1<<k)+1]);
}
int qmx(int l,int r){
    int k=(int)log2(r-l+1);
    return max(mn[k][l],mn[k][r-(1<<k)+1]);
}
void chk(int tp){
    static int st[N+5];
    int ss=0;
    for(int i=1;i<=n;i++){
        int p=gid(s[i]);
        if(p>0){
            mn[0][i]=i;
            st[++ss]=i;
        }
        else{
            mn[0][i]=0;
            if(ss&&gid(s[st[ss]])==-p){
                mn[0][i]=st[ss]; ss--;
            }
            else ss=0;
        }
    }
    for(int i=1;i<20;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
    for(int i=1;i<=m;i++){
        auto [l,r]=a[i];
        okl[i]&=qmn(l,r)>=l;
    }
    for(int i=n;i;i--){
        int p=-gid(s[i]);
        if(p>0){
            mn[0][i]=i;
            st[++ss]=i;
        }
        else{
            mn[0][i]=n+1;
            if(ss&&gid(s[st[ss]])==p){
                mn[0][i]=st[ss]; ss--;
            }
            else ss=0;
        }
    }
    for(int i=1;i<20;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            mn[i][j]=max(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
    for(int i=1;i<=m;i++){
        auto [l,r]=a[i];
        okr[i]&=qmx(l,r)<=r;
    }
}
void solve(){
    prep();
    scanf("%d %d",&n,&m);
    scanf("%s",s+1);
    vals[0]=I;
    for(int i=1;i<=n;i++){
        int p=gid(s[i]);
        if(p>0) vals[i]=vals[i-1]*v[p];
        else vals[i]=vals[i-1]*iv[-p];
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d",&a[i].l,&a[i].r);
        va[i]=(vals[a[i].l-1].geniv())*vals[a[i].r];
        okl[i]=okr[i]=1;
    }
    chk(0);
    for(int i=1;i<=m;i++)
        if(okr[i])
            cnt[va[i]]++;
    int ans=cnt[I]/2;
    for(int i=1;i<=m;i++){
        if((I<va[i]||va[i]<I)&&okl[i]){
            // printf("%d ",i);
            Mt iva=va[i].geniv();
            if(cnt[iva]){
                cnt[iva]--; ans++;
            }
        }
    }
    printf("%d\n",ans);
    cnt.clear();
}
int main(){
    int t; scanf("%d",&t);
    while(t--) solve();
    return 0;
}