#include<bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
#define vec vector<int>
#define int long long 
#define pb push_back
#define M 998244353
void in(int &x){
    int f=1;x=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')f=-1,c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
mt19937 rnd(time(0));
int t,n,m,k,x,y,z,fl;
char s[1000005];
struct Mat{
  int d[2][2];
  Mat operator *(const Mat &a)const{
    Mat res;
    res.d[0][0]=(d[0][0]*a.d[0][0]+d[0][1]*a.d[1][0])%M;
    res.d[0][1]=(d[0][0]*a.d[0][1]+d[0][1]*a.d[1][1])%M;
    res.d[1][0]=(d[1][0]*a.d[0][0]+d[1][1]*a.d[1][0])%M;
    res.d[1][1]=(d[1][0]*a.d[0][1]+d[1][1]*a.d[1][1])%M;
    return res;
  }
  bool test(){
    return (d[0][0]==1&&d[1][1]==1&&d[0][1]==0&&d[1][0]==0);
  }
  bool operator ==(const Mat &a)const{
    return d[0][0]==a.d[0][0]&&d[0][1]==a.d[0][1]&&d[1][0]==a.d[1][0]&&d[1][1]==a.d[1][1];
  }
  bool operator <(const Mat &a)const{
    if(d[0][0]!=a.d[0][0])return d[0][0]<a.d[0][0];
    if(d[0][1]!=a.d[0][1])return d[0][1]<a.d[0][1];
    if(d[1][0]!=a.d[1][0])return d[1][0]<a.d[1][0];
    return d[1][1]<a.d[1][1];
  }
  void print(){
    for(int i=0;i<2;i++){for(int j=0;j<2;j++)printf("%lld ",d[i][j]);puts("");}puts("");
  }
}B[4],V[4];
Mat ksm(Mat a,int m){
  Mat res;
  res.d[0][0]=res.d[1][1]=1;res.d[0][1]=res.d[1][0]=0;
  while(m){
    if(m&1)res=res*a;
    a=a*a;m/=2;
  }return res;
}
int pos[2000005];
struct node{
  Mat x,v;int l,r,sl,sr,ok,pl,pr;
}d[2000005];
node merge(node a,node b){
  node c;c.ok=0;
  c.l=a.l;c.r=b.r;
  if(!a.ok||!b.ok)return c;
  c.ok=1;c.x=a.x*b.x;c.v=b.v*a.v;
  c.pl=min(a.pl,b.pl);
  c.pr=max(a.pr,b.pr);
  if(!a.sr||!b.sl){
    c.sl=a.sl+b.sl;
    c.sr=a.sr+b.sr;
    return c;
  }
  if(a.sr>=b.sl){
    if(b.pl<a.l)c.ok=0;
    c.sl=a.sl;c.sr=b.sr+a.sr-b.sl;
  }
  else{
    if(a.pr>b.r)c.ok=0;
    c.sl=a.sl+b.sl-a.sr;c.sr=b.sr;
  }
  return c;
}
void build(int l,int r,int id){
  if(l==r){
    d[id].ok=1;d[id].l=d[id].r=l;
    if(s[l]=='(')d[id].x=B[0],d[id].v=V[0],d[id].sl=0,d[id].sr=1,d[id].pl=1e9,d[id].pr=pos[l];
    if(s[l]==')')d[id].x=V[0],d[id].v=B[0],d[id].sl=1,d[id].sr=0,d[id].pl=pos[l],d[id].pr=-1e9;
    if(s[l]=='[')d[id].x=B[1],d[id].v=V[1],d[id].sl=0,d[id].sr=1,d[id].pl=1e9,d[id].pr=pos[l];
    if(s[l]==']')d[id].x=V[1],d[id].v=B[1],d[id].sl=1,d[id].sr=0,d[id].pl=pos[l],d[id].pr=-1e9;
    if(s[l]=='{')d[id].x=B[2],d[id].v=V[2],d[id].sl=0,d[id].sr=1,d[id].pl=1e9,d[id].pr=pos[l];
    if(s[l]=='}')d[id].x=V[2],d[id].v=B[2],d[id].sl=1,d[id].sr=0,d[id].pl=pos[l],d[id].pr=-1e9;
    if(s[l]=='<')d[id].x=B[3],d[id].v=V[3],d[id].sl=0,d[id].sr=1,d[id].pl=1e9,d[id].pr=pos[l];
    if(s[l]=='>')d[id].x=V[3],d[id].v=B[3],d[id].sl=1,d[id].sr=0,d[id].pl=pos[l],d[id].pr=-1e9;
    return;
  }
  int mid=(l+r)/2;
  build(l,mid,id<<1);
  build(mid+1,r,id<<1|1);
  d[id]=merge(d[id<<1],d[id<<1|1]);
}
bool fir;node res;
void query(int l,int r,int id,int ql,int qr){
  if(ql<=l&&r<=qr){
    if(!fir)res=d[id],fir=1;
    else res=merge(res,d[id]);
    return;
  }
  int mid=(l+r)/2;
  if(ql<=mid)query(l,mid,id<<1,ql,qr);
  if(mid+1<=qr)query(mid+1,r,id<<1|1,ql,qr);
}
map<Mat,int>mp[2];
int st[4][1000005],top[4];
void solve(){
    in(n);in(m);
  scanf("%s",s+1);
  mp[0].clear();mp[1].clear();
  for(int i=0;i<4;i++)top[i]=0;
  for(int i=1;i<=n;i++)pos[i]=1e9;
  for(int i=1;i<=n;i++){
    int x=0,y=0;
    if(s[i]=='('||s[i]==')')x=0;
    if(s[i]=='['||s[i]==']')x=1;
    if(s[i]=='{'||s[i]=='}')x=2;
    if(s[i]=='<'||s[i]=='>')x=3;
    if(s[i]==')'||s[i]==']'||s[i]=='}'||s[i]=='>')y=1;
    if(y==0){st[x][++top[x]]=i;continue;}
    else if(!top[x])pos[i]=-1e9;
    else{
      bool ok=1;
      for(int j=0;j<4;j++)if(top[j]&&st[j][top[j]]>st[x][top[x]])ok=0;
      if(!ok)pos[i]=-1e9;
        else{
          int u=st[x][top[x]--];
          pos[u]=i;pos[i]=u;
        }
    }
    if(pos[i]<0)for(int j=0;j<4;j++)top[j]=0;
  }
  build(1,n,1);
  int ans=0,sum=0;
  for(int i=1;i<=m;i++){
    in(x);in(y);
    fir=0;query(1,n,1,x,y);
    if(!res.ok)continue;
    if(res.sl&&res.sr)continue;
    if(res.x.test()){sum++;continue;}
    int tp=0;if(res.sl)tp=1;
    if(mp[tp^1][res.v])mp[tp^1][res.v]--,ans++;
    else mp[tp][res.x]++;
  }
  printf("%lld\n",ans+sum/2);
}
signed main(){
    for(int u=0;u<4;u++){
      while(1){
        for(int i=0;i<2;i++)for(int j=0;j<2;j++)B[u].d[i][j]=rnd()%M;
        V[u]=ksm(B[u],M-2);
        Mat I=B[u]*V[u];
        if(I.test())break;
    }
  }
  in(t);
  while(t--)solve();
  
}