#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (u<<1)
#define rson (u<<1|1)
const ll N=500007,MOD=998244353;
ll qpow(ll x,ll k){
	ll sum=1;x%=MOD;
	while(k){
		if (k&1) (sum*=x)%=MOD;
		(x*=x)%=MOD;k>>=1;
	}
	return sum;
}
struct Matrix{
	ll a,b,c,d;
	Matrix(){a=d=1;b=c=0;}
	Matrix(ll A,ll B,ll C,ll D){a=A;b=B;c=C;d=D;}
	bool inv(){
		ll v=qpow((a*d-b*c)%MOD+MOD,MOD-2);
		if (!v) return 0;
		swap(a,d);
		(a*=v)%=MOD;(b*=MOD-v)%=MOD;(c*=MOD-v)%=MOD;(d*=v)%=MOD;
		return 1;
	}
	pair<ll,ll> get(){
		return make_pair(a*MOD+b,c*MOD+d);
	}
}A[N],B[N],M[4][2],M1[N<<2],M2[N<<2],I;
Matrix operator *(const Matrix& a,const Matrix& b){
	return Matrix((a.a*b.a+a.b*b.c)%MOD,(a.a*b.b+a.b*b.d)%MOD,(a.c*b.a+a.d*b.c)%MOD,(a.c*b.b+a.d*b.d)%MOD);
}
bool operator ==(const Matrix& a,const Matrix& b){
	return a.a==b.a&&a.b==b.b&&a.c==b.c&&a.d==b.d;
}
mt19937 rng(time(0));
int T,n,m,l[N],r[N],pre[N],suf[N],ans,sum0,mxL[N],stk[N],top,L[4][N],R[4][N],type[N],PRE[N<<2],SUF[N<<2];
char s[N],c[4][3]={"()","[]","{}","<>"};
map<pair<ll,ll>,ll> mp1,mp2;
map<char,char> rev;
int myrand(int l=0,int r=MOD-1){return uniform_int_distribution<int>(l,r)(rng);}
void build(int u,int l,int r){
	if (l==r){
		PRE[u]=pre[l];SUF[u]=suf[l];
//		M1[u]=A[l];M2[u]=B[l];
		return;
	}
	int mid=l+r>>1;
	build(lson,l,mid);build(rson,mid+1,r);
	PRE[u]=min(PRE[lson],PRE[rson]);SUF[u]=min(SUF[lson],SUF[rson]);
//	M1[u]=M1[lson]*M1[rson];M2[u]=M2[rson]*M2[lson];
}
void build2(int u,int l,int r){
	if (l==r){
//		PRE[u]=pre[l];SUF[u]=suf[l];
		M1[u]=A[l];M2[u]=B[l];
		return;
	}
	int mid=l+r>>1;
	build2(lson,l,mid);build2(rson,mid+1,r);
//	PRE[u]=min(PRE[lson],PRE[rson]);SUF[u]=min(SUF[lson],SUF[rson]);
	M1[u]=M1[lson]*M1[rson];M2[u]=M2[rson]*M2[lson];
}
Matrix query1(int u,int l,int r,int L,int R){
	if (L<=l&&r<=R) return M1[u];
	int mid=l+r>>1;
	if (R<=mid) return query1(lson,l,mid,L,R);
	if (L>mid) return query1(rson,mid+1,r,L,R);
	return query1(lson,l,mid,L,R)*query1(rson,mid+1,r,L,R);
}
Matrix query2(int u,int l,int r,int L,int R){
	if (L<=l&&r<=R) return M2[u];
	int mid=l+r>>1;
	if (R<=mid) return query2(lson,l,mid,L,R);
	if (L>mid) return query2(rson,mid+1,r,L,R);
	return query2(rson,mid+1,r,L,R)*query2(lson,l,mid,L,R);
}
int queryP(int u,int l,int r,int L,int R){
	if (L<=l&&r<=R) return PRE[u];
	int mid=l+r>>1;
	if (R<=mid) return queryP(lson,l,mid,L,R);
	if (L>mid) return queryP(rson,mid+1,r,L,R);
	return min(queryP(lson,l,mid,L,R),queryP(rson,mid+1,r,L,R));
}
int queryS(int u,int l,int r,int L,int R){
	if (L<=l&&r<=R) return SUF[u];
	int mid=l+r>>1;
	if (R<=mid) return queryS(lson,l,mid,L,R);
	if (L>mid) return queryS(rson,mid+1,r,L,R);
	return min(queryS(lson,l,mid,L,R),queryS(rson,mid+1,r,L,R));
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	for (int o=0;o<4;++o){
		rev[c[o][1]]=c[o][0];
		M[o][0]=Matrix(myrand(),myrand(),myrand(),myrand());
		while(1){
			M[o][1]=M[o][0];
			if (M[o][1].inv()) break;
		}
		assert(M[o][0]*M[o][1]==I);
	}
	while(T--){
		cin>>n>>m>>(s+1);ans=sum0=0;mp1.clear();mp2.clear();
		top=0;
		for (int i=1;i<=n;++i){
			mxL[i]=mxL[i-1];
			if (s[i]=='('||s[i]=='['||s[i]=='<'||s[i]=='{') stk[++top]=i;
			else{
				if (top&&s[stk[top]]!=rev[s[i]]){
					mxL[i]=stk[top]+1;top=0;
				}
				else top=max(top-1,0);
			}
		}
		for (int i=1;i<=m;++i){cin>>l[i]>>r[i];type[i]=3*(l[i]<mxL[r[i]]);}suf[n+1]=0;
		for (int o=0;o<4;++o){
			for (int i=1;i<=n;++i){
				pre[i]=pre[i-1];
				if (s[i]==c[o][0]){A[i]=M[o][0];B[i]=M[o][1];++pre[i];}
				if (s[i]==c[o][1]){A[i]=M[o][1];B[i]=M[o][0];--pre[i];}
			}
			for (int i=n;i;--i){
				suf[i]=suf[i+1];
				if (s[i]==c[o][1]) ++suf[i];
				if (s[i]==c[o][0]) --suf[i];
			}
			build(1,0,n+1);
			for (int i=1;i<=m;++i){
				L[o][i]=pre[r[i]]-queryP(1,0,n+1,l[i]-1,r[i]-1);
				R[o][i]=suf[l[i]]-queryS(1,0,n+1,l[i]+1,r[i]+1);
				if (L[o][i]<0) L[o][i]=0;
				if (R[o][i]<0) R[o][i]=0;
				if (L[o][i]) type[i]|=1;
				if (R[o][i]) type[i]|=2;
			}
		}
		build2(1,1,n);
		for (int i=1;i<=m;++i){
			if (type[i]==0) ++sum0;
			if (type[i]==3) continue;
			if (type[i]==1){
				auto p=query1(1,1,n,l[i],r[i]).get();
				if (mp1.find(p)==mp1.end()) mp1[p]=1;else ++mp1[p];
			}
			if (type[i]==2){
				auto p=query2(1,1,n,l[i],r[i]).get();
				if (mp2.find(p)==mp2.end()) mp2[p]=1;else ++mp2[p];
			}
		}
		for (auto p:mp1) if (mp2.find(p.first)!=mp2.end()) ans+=min(p.second,mp2[p.first]);
		cout<<ans+sum0/2<<'\n';
	}
	return 0;
}