#include<bits/stdc++.h>

#define pii pair<int,int>
#define maxn 500005
#define INF 1e18

using namespace std;

inline int read(){
    int lre=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(isdigit(c)){
        lre=(lre<<3)+(lre<<1)+(c-'0');
        c=getchar();
    }
    return lre*f;
}

struct seg_tree{
	int tot;
	int lc[2*maxn],rc[2*maxn];
	int delta[2*maxn];
	void push_down(int x){
		if(delta[x]){
			delta[lc[x]]=delta[rc[x]]=delta[x];
			delta[x]=0;
		} 
	}
	void build(int x,int l,int r){
		delta[x]=0;
		if(l==r){
			return;
		}
		int mid=l+r>>1;
		lc[x]=tot++;
		build(lc[x],l,mid);
		rc[x]=tot++;
		build(rc[x],mid+1,r);
	}
	void change(int x,int l,int r,int ql,int qr,int val){
		if(ql<=l&&r<=qr){
			delta[x]=val;
			return;
		}
		push_down(x);
		int mid=l+r>>1;
		if(ql<=mid){
			change(lc[x],l,mid,ql,qr,val);
		}
		if(qr>mid){
			change(rc[x],mid+1,r,ql,qr,val);
		}
	}
	bool query(int x,int l,int r,int goal){
		if(l==r){
			return delta[x]&1;
		}
		push_down(x);
		int mid=l+r>>1;
		if(goal<=mid){
			return query(lc[x],l,mid,goal);
		}else{
			return query(rc[x],mid+1,r,goal);
		}
	}
}seg;

const int base=10;
const int mod[2]={998244353,988244533};
int pw[maxn][3];

int n,m,res;
string str;
int arr[maxn];
int l[maxn],r[maxn];
pii ha[maxn];//哈希值的获取 
map<pii,int> mp;

void init(){
	for(int i=1;i<=m;i++)ha[i].first=ha[i].second=-1;
}

void rev(){
	for(int i=1;i<=n;i++){
		arr[i]*=-1;
	}
	reverse(arr+1,arr+n+1);
	for(int i=1;i<=m;i++){
		l[i]=n-l[i]+1;r[i]=n-r[i]+1;
		swap(l[i],r[i]);
	}
}

vector<pii> v[maxn];
int tp=0,lst=0;
int st[maxn];
pii a[maxn];//哈希 

void calc(){
	for(int i=1;i<=n;i++)v[i].clear();
	for(int i=1;i<=m;++i){
		v[r[i]].push_back(make_pair(l[i],i));
	}
	tp=0;lst=0;st[0]=0;
	a[0].first=a[0].second=0;
	for(int i=1;i<=n;i++){
	//	cout<<"i="<<i<<"!insert "<<arr[i]<<endl;
		if(tp&&arr[st[tp]]+arr[i]==0){
			int L=st[tp]+1,R=i;
			if(L<=R){
				seg.change(0,1,n,L,R,1);//线段树记录括号匹配的内部节点 
			}
			tp--; 
		//	cout<<"pop!"<<endl;
		}else if(arr[i]>=0){
			st[++tp]=i;
		//	cout<<"insert new!"<<endl;
			a[tp].first=(1ll*a[tp-1].first*base%mod[0]+arr[i])%mod[0];
			a[tp].second=(1ll*a[tp-1].second*base%mod[1]+arr[i])%mod[1];
		}else{
		//	cout<<"i="<<i<<" cut!"<<endl;
			tp=0;
			st[0]=i;
			lst=i;
			continue;
			//直接跳过 
		}
		for(pii p:v[i]){
			int L=p.first,x=p.second;
			if(L<=lst)continue;
			if(seg.query(0,1,n,L))continue;
			int ind=lower_bound(st+1,st+tp+1,L)-st;
			ha[x].first=(a[tp].first-1ll*a[ind-1].first*pw[tp-ind+1][0]%mod[0]+mod[0])%mod[0];
			ha[x].second=(a[tp].second-1ll*a[ind-1].second*pw[tp-ind+1][1]%mod[1]+mod[1])%mod[1];
		}
	}
}

void solve(){
	n=read();m=read();
	cin>>str;str=' '+str;
	for(int i=1;i<=n;i++){
		if(str[i]=='(')arr[i]=1;
		if(str[i]=='[')arr[i]=2;
		if(str[i]=='{')arr[i]=3;
		if(str[i]=='<')arr[i]=4;
		if(str[i]==')')arr[i]=-1;
		if(str[i]==']')arr[i]=-2;
		if(str[i]=='}')arr[i]=-3;
		if(str[i]=='>')arr[i]=-4;
	}
	for(int i=1;i<=m;i++){
		l[i]=read();r[i]=read();
//		for(int j=l[i];j<=r[i];j++){
//			putchar(str[j]); 
//		}
//		putchar('\n');
	}
	
	seg.tot=1;seg.build(0,1,n); 
	
	mp.clear();init();seg.change(0,1,n,1,n,2);
	calc();
//	cout<<"solve 1"<<endl;
	for(int i=1;i<=m;i++){
	//	cout<<"("<<ha[i].first<<","<<ha[i].second<<") ";
		if(ha[i].first!=-1){
			mp[ha[i]]++;
		}
	}
//	cout<<endl;
	rev();init();seg.change(0,1,n,1,n,2);
	calc();
	res=0;
//	cout<<"solve 2"<<endl;
	for(int i=1;i<=m;i++){
	//	cout<<"("<<ha[i].first<<","<<ha[i].second<<") ";
		if(ha[i].first==0&&ha[i].second==0){
			continue;
		}
		if(ha[i].first!=-1&&mp[ha[i]]){
			res++;
			mp[ha[i]]--;
		}
	}
//	cout<<endl;
	res+=mp[make_pair(0,0)]/2;
	printf("%d\n",res);
}

signed main(){
	
//	freopen("ex_1.in","r",stdin);
	
	pw[0][0]=pw[0][1]=1;
	for(int i=1;i<=500000;i++){
		pw[i][0]=1ll*pw[i-1][0]*base%mod[0];
		pw[i][1]=1ll*pw[i-1][1]*base%mod[1];
	}
	
	int t=read();
	while(t--){
		solve();
	}
	
	return 0;
} 
/*
1
20 10
[()]]([[]([)(][]([)(
2 3
7 18
10 20
2 17
6 9
3 20
9 20
3 13
3 3
12 17

0
*/