#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read(){
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define mod 998244353
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 500005
#define inf 0x3f3f3f3f

struct mat{
	modint a[2][2];
	modint*operator[](int x){return a[x];}
	mat(modint A=0,modint B=0,modint C=0,modint D=0){a[0][0]=A,a[0][1]=B,a[1][0]=C,a[1][1]=D;}
	mat operator *(mat b)const{
		return mat(
			a[0][0]*b[0][0]+a[0][1]*b[1][0],
			a[0][0]*b[0][1]+a[0][1]*b[1][1],
			a[1][0]*b[0][0]+a[1][1]*b[1][0],
			a[1][0]*b[0][1]+a[1][1]*b[1][1] 
		);
	}
	bool operator < (const mat &o) const {
		For(i,0,1) For(j,0,1){
			if (a[i][j].x==o.a[i][j].x) continue;
			if (a[i][j].x<o.a[i][j].x) return 1;
			return 0;
		}
		return 0;
	}
	bool operator == (const mat &o) const {
		For(i,0,1) For(j,0,1) if (a[i][j].x!=o.a[i][j].x) return 0;
		return 1;
	}
	void print(){
		For(i,0,1){
			For(j,0,1) printf("%d ",a[i][j].x);
			puts("");
		}
	}
};

mt19937_64 rnd(198964);
int a[maxn];
mat val[5],fval[5];

mat gen(){
	mat a;
	For(i,0,1)For(j,0,1)a[i][j]=rnd()%(mod-1)+1;
	return a;
}
int pi[505],pj[505];
bool getinv(mat&a){
	mat tmp=a;
	For(k,0,1){
		For(i,k,1)
			For(j,k,1)
				if(a[i][j].x){pi[k]=i,pj[k]=j;break;}
		For(i,0,1)swap(a[k][i],a[pi[k]][i]);
		For(i,0,1)swap(a[i][k],a[i][pj[k]]);
		if(!a[k][k].x)return 0;
		a[k][k]=1/a[k][k];
		For(j,0,1)if(j!=k)a[k][j]*=a[k][k];
		For(i,0,1)if(i!=k)For(j,0,1)if(j!=k)a[i][j]-=a[i][k]*a[k][j];
		For(i,0,1)if(i!=k)a[i][k]=-a[i][k]*a[k][k];
	}
	Rep(k,1,0){
		For(i,0,1)swap(a[pj[k]][i],a[k][i]);
		For(i,0,1)swap(a[i][pi[k]],a[i][k]);
	}
	tmp=tmp*a;
	return 1;
}

#define mp make_pair
typedef pair<int,int> pa;
const int N = 5e5+10;
int n,m;
char s[N];
mat L[N],R[N],pre[N],inv[N],ycl[10];
pa p[N];

int get(char c){
	if (c=='(') return 0;
	if (c=='[') return 1;
	if (c=='{') return 2;
	if (c=='<') return 3;
	if (c==')') return 4;
	if (c==']') return 5;
	if (c=='}') return 6;
	if (c=='>') return 7;
}

vector<pa>Q[N];
int top;
pa stk[N];
bool flag[N][2];
struct BIT{
	int n,c[N];
	inline void init(int _n){
		n=_n;
		For(i,1,n) c[i]=0;
	}
	inline void Add(int x,int y){
		for (;x<=n;x+=x&-x) c[x]+=y;
	}
	inline int Query(int x){
		int ret=0;
		for (;x;x-=x&-x) ret+=c[x];
		return ret;
	}
	inline int Query(int l,int r){
		return Query(r)-Query(l-1);
	}
}T1;

int mn[N][22];
inline int Query(int l,int r){
	int t=__lg(r-l+1);
	return min(mn[r][t],mn[l+(1<<t)-1][t]);
}

inline void solve(){
	n=read(),m=read();
	scanf("%s",s+1);
//	n=rand()%10+1,m=rand()%10+1;
//	For(i,1,n) s[i]="()[]{}<>"[rand()%8];
	pre[0]=mat(1,0,0,1);
	inv[0]=mat(1,0,0,1);
	For(i,1,n){
		pre[i]=pre[i-1]*ycl[get(s[i])];
		inv[i]=ycl[get(s[i])^4]*inv[i-1];
	}
	For(i,1,n) Q[i].clear();
	For(i,1,m){
		p[i].fi=read();
		p[i].se=read();
//		p[i].fi=rand()%n+1;
//		p[i].se=rand()%n+1;
//		if (p[i].fi>p[i].se) swap(p[i].fi,p[i].se);
		Q[p[i].se].pb(mp(p[i].fi,i));
		flag[i][0]=flag[i][1]=0;
	}
	T1.init(n);
	top=0;
	For(i,1,n){
		int t=get(s[i]),L=n;
		if (t<=3){
			stk[++top]=mp(t,i);
			T1.Add(i,1);
		} else if (top&&stk[top].fi==t-4){
			L=stk[top].se;
			T1.Add(stk[top].se,-1);
			--top;
		} else {
			L=0;
			stk[++top]=mp(t,i);
		}
		mn[i][0]=L;
		For(j,1,__lg(i)) mn[i][j]=min(mn[i][j-1],mn[i-(1<<(j-1))][j-1]);
		for (auto [l,id]:Q[i]){
			flag[id][0]=(T1.Query(l,i)>0);
			flag[id][1]=Query(l,i)<l;
		}
	}
	int cnt=0,ans=0;
	map<mat,int>f;
	For(i,1,m){
		auto [l,r]=p[i];
		if (flag[i][0]&&flag[i][1]) continue;
		mat v1=inv[l-1]*pre[r];
		mat v2=v1;
		getinv(v2);
		if (f[v2]) --f[v2],++ans;
			else ++f[v1];
	}
	ans+=cnt/2;
	printf("%d\n",ans);
}

int main(){
	//freopen("b.out","w",stdout);
    int T=read();
	//int T=10000;
	For(i,0,3){
		while (2333){
			ycl[i]=ycl[i+4]=gen();
			if (getinv(ycl[i+4])) break;
		}
	}
	while (T--) solve();
}
/*
4
8 1
()[]{}<>
3 6

2 6
)(
1 1
1 1
1 1
2 2
2 2
2 2

6 2
([)(])
1 3
4 6

22 8
([{}<<<<])>>>>([]){()}
3 8
11 14
1 10
3 4
19 22
20 21
17 20
21 22
*/