#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
typedef unsigned long long ull;
using namespace std;
struct freader {
    FILE *f;
#   ifdef ONLINE_JUDGE
    char buf[1048577], *p1, *p2;
#       define fgetc(f) (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1048576, f), p1 == p2) ? EOF : *p1++)
#   endif
#   ifdef BOOLTRANS
    bool neof;
#       define NEOF(c) ((c) != EOF || (neof = 0))
#   else
#       define NEOF(c) ((c) != EOF)
#   endif
    freader(FILE *_f = stdin) : f(_f) {
#       ifdef BOOLTRANS
        neof = 1;
#       endif
#       ifdef ONLINE_JUDGE
        setvbuf(f, NULL, _IONBF, 0);
        p1 = p2 = buf;
#       endif
    }
    void read(char &x) {
        for (x = fgetc(f); NEOF(x) && x <= ' '; x = fgetc(f));
        return;
    }
    void read(char *s) {
        for (*s = fgetc(f); NEOF(*s) && *s <= ' '; *s = fgetc(f));
        for (s++; NEOF(*s = fgetc(f)) && *s > ' '; s++);
        *s = '\0';
        return;
    }
    void read(float x) {return fputs("Error: Unable to read float.", stderr), void();}
    void read(double x) {return fputs("Error: Unable to read double.", stderr), void();}
    void read(long double x) {return fputs("Error: Unable to read long double.", stderr), void();}
    template<typename T> void read(T &x) {
        char c(fgetc(f));
#       ifdef NEGATIVE
        for (; NEOF(c) && (c < '0' || c > '9') && c != '-'; c = fgetc(f));
        if (c == '-')
            for (c = fgetc(f), x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) - (c ^ '0');
        else
            for (x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) + (c ^ '0');
#       else
        for (; NEOF(c) && (c < '0' || c > '9'); c = fgetc(f));
        for (x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) + (c ^ '0');
#       endif
        return;
    }
#   if __cplusplus >= 201103
    template<typename T, typename...Args> void read(T &x, Args &...args) {return read(x), read(args...);}
#   endif
    template<typename T> freader &operator >> (T &x) {
#       ifdef BOOLTRANS
        return *this ? read(x), *this : *this;
#       else
        return read(x), *this;
#       endif
    }
#   ifdef BOOLTRANS
    operator bool() {return neof;}
#   endif
#   ifdef ONLINE_JUDGE
#       undef fgetc
#   endif
#   undef NEOF
} fin;
int T,n,m,pos[500005];
char str[500005];
int stk[500005],tp;
char op[1005];
bool ck(int x,int y){
	if(str[x]=='('&&str[y]==')')return 1;
	if(str[x]=='['&&str[y]==']')return 1;
	if(str[x]=='{'&&str[y]=='}')return 1;
	if(str[x]=='<'&&str[y]=='>')return 1;
	return 0;
}
int type[500005],opt[500005];
const ull seed=233;
ull hsh[500005];
unordered_map<ull,int>vis;
struct node{
	int pos,id;
	node(int pos_,int id_){
		pos=pos_,id=id_;
	}
};
vector<node>vec1[500005],vec2[500005];
ull pw[500005];
struct shit{
	ull hsh1,hsh2;
	int len;
	shit(){}
	shit(ull hsh1_,ull hsh2_,int len_){
		hsh1=hsh1_,hsh2=hsh2_,len=len_;
	}
};
struct SGT{
	int l,r;
	shit val;
}Tree[2000005];
vector<pii>vec[500005];
void ztree(int p,int l,int r){
	Tree[p].l=l,Tree[p].r=r;
	Tree[p].val=shit(0,0,0);
	if(l==r)return;
	int mid=l+r>>1;
	ztree(p*2,l,mid);
	ztree(p*2+1,mid+1,r);
}
shit merge(shit vl,shit vr){
	ull hsh1=vl.hsh1*pw[vr.len]+vr.hsh1;
	ull hsh2=vr.hsh2*pw[vl.len]+vl.hsh2;
	return shit(hsh1,hsh2,vl.len+vr.len);
}
void upd(int p,int x,ull v){
	if(Tree[p].l==Tree[p].r){
		Tree[p].val=shit(v,v,(v>0));
		return;
	}
	int mid=Tree[p].l+Tree[p].r>>1;
	if(x<=mid)upd(p*2,x,v);
	else upd(p*2+1,x,v);
	Tree[p].val=merge(Tree[p*2].val,Tree[p*2+1].val);
}
shit Get(int p,int l,int r){
	if(l<=Tree[p].l&&Tree[p].r<=r)return Tree[p].val;
	int mid=Tree[p].l+Tree[p].r>>1;
	shit vl,vr;bool fl0=0,fl1=0;
	if(l<=mid)vl=Get(p*2,l,r),fl0=1;
	if(r>mid)vr=Get(p*2+1,l,r),fl1=1;
	if(fl0&&fl1)return merge(vl,vr);
	if(fl0)return vl;
	return vr;
}
int main(){
	op['(']=')',op[')']='(';
	op['[']=']',op[']']='[';
	op['{']='}',op['}']='{';
	op['<']='>',op['>']='<';
	fin.read(T);
	pw[0]=1;
	for(int i=1;i<=5e5;i++)pw[i]=pw[i-1]*seed;
	while(T--){
		fin.read(n,m);
		fin.read(str+1); 
		for(int i=1;i<=n;i++){
			if(str[i]=='('||str[i]=='<'||str[i]=='['||str[i]=='{')pos[i]=n+1,opt[i]=0;
			else pos[i]=0,opt[i]=1;
		}
		for(int i=1;i<=n;i++){
			if(tp>0&&ck(stk[tp],i))pos[stk[tp]]=i,pos[i]=stk[tp],tp--;
			else stk[++tp]=i;
			vec1[i].clear(),vec2[i].clear();
		}
		int sum=0,ans=0;
		for(int i=1;i<=m;i++){
			type[i]=0;
			int l,r;
			fin.read(l,r);
			vec1[r].push_back(node(l,i));
			vec2[l].push_back(node(r,i));
		}
		ztree(1,1,n);
		for(int i=1;i<=n;i++)vec[i].clear();
		for(int i=1;i<=n;i++){
			if(opt[i]==0)vec[i].push_back(mp(i,str[i])),vec[pos[i]].push_back(mp(i,0));
		}
		for(int i=1;i<=n;i++){
			for(auto to:vec[i])upd(1,to.fi,to.se);
			for(auto to:vec1[i]){
				shit val=Get(1,to.pos,i);
				if(val.hsh1)type[to.id]+=2,hsh[to.id]=val.hsh1;
			}
		}
		ztree(1,1,n);
		for(int i=1;i<=n;i++)vec[i].clear();
		for(int i=1;i<=n;i++){
			if(opt[i]==1)vec[i].push_back(mp(i,op[str[i]])),vec[pos[i]].push_back(mp(i,0));
		}
		for(int i=n;i;i--){
			for(auto to:vec[i])upd(1,to.fi,to.se);
			for(auto to:vec2[i]){
				shit val=Get(1,i,to.pos);
				if(val.hsh2)type[to.id]+=1,hsh[to.id]=val.hsh2;
			}
		}
		for(int i=1;i<=m;i++)sum+=(!type[i]);
		ans=sum/2;
		vis.clear();
		for(int i=1;i<=m;i++){
			if(type[i]==2)vis[hsh[i]]++;
		}
		for(int i=1;i<=m;i++){
			if(type[i]==1&&vis[hsh[i]]>0)ans++,vis[hsh[i]]--;
		}
		printf("%d\n",ans);
	}
	return 0;
}