#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline ll read(){
	ll s=0,k=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-') k=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*k;
}

const int N=5e5+10,B=31;
int n,m,a[N],top,st[N],pos[N],id[N];
vector<int>L[N],R[N];
map<ll,int> ml,mr;
ll fac[N],hsa[N],zero;
char s[N];

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

ll calc(int l,int r){
	return hsa[r]-hsa[l-1]*fac[r-l+1];
}

void solve(map<ll,int> &mp,vector<int> q[]){
	top=0;
	int lim=0;
	for(int i=1;i<=n;i++){
		if(a[i]&1){
			if(a[st[top]]!=(a[i]^1)) top=0,lim=i;
			else top--;
		}
		else{
			st[++top]=i;
			hsa[top]=hsa[top-1]*B+a[i];
		}
		pos[i]=top;
		id[i]=st[top];
		for(auto x:q[i])
			if(x>=lim&&top>=pos[x]&&st[pos[x]]==id[x]){
				if(pos[x]==top) zero++;
				else mp[calc(pos[x]+1,top)]++;
			}
	}
}

void solve(){
	n=read();m=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		L[i].clear();
		R[i].clear();
		a[i]=get(s[i]);
	}
	ml.clear(); mr.clear();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		L[r].push_back(l-1);
		R[n-l+1].push_back(n-r);
	}
	zero=0;
	solve(ml,L);
	reverse(a+1,a+1+n);
	for(int i=1;i<=n;i++) a[i]^=1;
	solve(mr,R);
	zero>>=2;
	for(auto x:ml) zero+=min(x.second,mr[x.first]);
	printf("%lld\n",zero);
}

int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	fac[0]=1;
	for(int i=1;i<=500000;i++) fac[i]=fac[i-1]*B;
	int T=read();
	while(T--) solve();
	return 0;
}