#include <bits/stdc++.h>
#define N 500011
#define s1 first
#define s2 second
using namespace std;
const int P[2]={1028838407,1013333903};
inline int qpow(int bs,int ex,int p){int ans=1;while(ex){if(ex&1)ans=1ll*ans*bs%p;ex>>=1;bs=1ll*bs*bs%p;}return ans;}
struct mint{int x[2];mint(){x[0]=x[1]=0;}mint(int _x){x[0]=_x;x[1]=_x;}mint(int _a,int _b){x[0]=_a;x[1]=_b;}};
mint operator+(mint a,mint b){return mint((a.x[0]+b.x[0])%P[0],(a.x[1]+b.x[1])%P[1]);}
mint operator-(mint a,mint b){return mint((a.x[0]+P[0]-b.x[0])%P[0],(a.x[1]+P[1]-b.x[1])%P[1]);}
mint operator*(mint a,mint b){return mint(1ll*a.x[0]*b.x[0]%P[0],1ll*a.x[1]*b.x[1]%P[1]);}
bool operator==(mint a,mint b){return a.x[0]==b.x[0]&&a.x[1]==b.x[1];}
bool operator!=(mint a,mint b){return !(a==b);}
bool operator<(mint a,mint b){return a.x[0]<b.x[0]||a.x[0]==b.x[0]&&a.x[1]<b.x[1];}
mint pw[N];
int T,n,m;char s[N];
const mint B=100;
struct kueri{int l,r,id;};
vector<kueri> vr[N],vl[N];
pair<char,int> stk[N];int sn;
mint Hs[N],ansl[N],ansr[N];bool ban[N];
bool isR(char c){return c=='}'||c=='>'||c==')'||c==']';}
int intC(char c)
{
	if(c=='<'||c=='>')return 1;
	if(c=='('||c==')')return 2;
	if(c=='['||c==']')return 3;
	if(c=='{'||c=='}')return 5;
	return 0;
}
char pairC(char c)
{
	if(c=='<'||c=='>')return '<'^'>'^c;
	if(c=='('||c==')')return '('^')'^c;
	if(c=='['||c==']')return '['^']'^c;
	if(c=='{'||c=='}')return '{'^'}'^c;
	return 0;
}
void procL()
{
	// printf("============================procL()\n");
	sn=0;
	int nok=0;
	for(int i=1;i<=n;++i)
	{
		// printf("i:%d\n",i);
		if(isR(s[i]))
		{
			if(sn)
			{
				if(stk[sn].s1==pairC(s[i]))--sn;
				else nok=stk[sn].s2;
			}
		}
		else
		{
			stk[++sn]=make_pair(s[i],i);
			Hs[sn]=Hs[sn-1]*B+intC(s[i]);
		}
		// printf("stk:");for(int i=1;i<=sn;++i)printf("{%c,%d} ",stk[i].s1,stk[i].s2);putchar(10);
		for(kueri k:vr[i])
		{
			// printf("k:{[%d,%d],id:%d}\n",k.l,k.r,k.id);
			if(k.l<=nok)ban[k.id]=1;//,printf("banned\n");
			else
			{
				int L=1,R=sn,id=sn+1;
				while(L<=R)
				{
					int M=L+R>>1;
					if(stk[M].s2>=k.l)id=M,R=M-1;else L=M+1;
				}
				ansl[k.id]=Hs[sn]-Hs[id-1]*pw[sn-id+1];
			}
		}
	}
}
void procR()
{
	// printf("============================procR()\n");
	sn=0;
	int nok=n+1;
	for(int i=n;i;--i)
	{
		if(!isR(s[i]))
		{
			if(sn)
			{
				if(stk[sn].s1==pairC(s[i]))--sn;
				else nok=stk[sn].s2;
			}
		}
		else
		{
			stk[++sn]=make_pair(s[i],i);
			Hs[sn]=Hs[sn-1]*B+intC(s[i]);
		}
		// printf("stk:");for(int i=1;i<=sn;++i)printf("{%c,%d} ",stk[i].s1,stk[i].s2);putchar(10);
		for(kueri k:vl[i])
		{
			// printf("k:{[%d,%d],id:%d}\n",k.l,k.r,k.id);
			if(k.r>=nok)ban[k.id]=1;//,printf("banned\n");
			else
			{
				int L=1,R=sn,id=sn+1;
				while(L<=R)
				{
					int M=L+R>>1;
					if(stk[M].s2<=k.r)id=M,R=M-1;else L=M+1;
				}
				ansr[k.id]=Hs[sn]-Hs[id-1]*pw[sn-id+1];
			}
		}
	}
}
set<pair<mint,int> > st;
int main()
{
	scanf("%d",&T);while(T--)
	{
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		pw[0]=1;for(int i=1;i<=n;++i)pw[i]=pw[i-1]*B;
		for(int i=1;i<=n;++i)vl[i].clear(),vr[i].clear();
		for(int i=1;i<=m;++i)
		{
			int l,r;scanf("%d%d",&l,&r);
			vr[r].push_back({l,r,i});
			vl[l].push_back({l,r,i});ban[i]=0;
		}
		procL();
		procR();
		// for(int i=1;i<=m;++i)
		// {
		// 	printf("ansl:{%d,%d} ansr:{%d,%d} ban:%d\n",ansl[i].x[0],ansl[i].x[1],ansr[i].x[0],ansr[i].x[1],ban[i]);
		// }
		st.clear();
		int cnt=0;
		int zero=0;
		for(int i=1;i<=m;++i)
		{
			if(ansl[i]!=0&&ansr[i]!=0)ban[i]=1;
			if(!ban[i]&&ansl[i]==0&&ansr[i]==0)++zero;
		}
		cnt=zero/2;
		for(int i=1;i<=m;++i)
		{
			if(!ban[i]&&ansl[i]!=0)
			{
				st.insert({ansl[i],i});
			}
		}
		for(int i=1;i<=m;++i)
		{
			if(!ban[i]&&ansr[i]!=0)
			{
				auto it=st.lower_bound({ansr[i],0});
				if(it!=st.end()&&it->s1==ansr[i])
				{
					++cnt;
					st.erase(it);
				}
			}
		}
		printf("%d\n",cnt);
	}
}