#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll x,ll y){ return x+rnd()%(y-x+1); }
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const ll mod = (ll)1e18 + 3;
ll  base = rng(1, mod-1);
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
int id[256], p[256];
int n,m;
char s[500005];
struct Node{
	int l,r,id;
}t[500005];

ll lft[500005], rht[500005], pw[500005], fa[500005], col[500005];
bool match(ll a,ll b){ return id[s[a]]+id[s[b]]==0; }
int stk[500005], tp; ll hsh[500005];

int find(int x){
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
void merge(int x,int y){
	if(x<1 || y>n) return;
	x=find(x), y=find(y);
	if(x==y) return;
	fa[x] = y;
}
void color(int L,int R){
	R++;
	while(L<=R){
		col[L]=1;
		merge(L, L+1);
		L++;
		if(col[L]) L=find(L);
	}

	// for(int i=L;i<=R;i++) col[i]=1;
}
ll gethash(int l,int r){
	if(l>r) return 0;
	return (hsh[r]+(__int128)(mod-hsh[l-1])*pw[r-l+1])%mod;
}

unordered_map<ll,ll>mp1, mp2;
void procedure(){
	n=read(),m=read();
	mp1.clear(); mp2.clear();
	scanf("%s", s+1);
	for(int i=1;i<=m;i++){
		t[i].l=read(), t[i].r=read(), t[i].id=i;
		lft[i]=rht[i]=0;
	}

	{
		sort(t+1, t+m+1, [](Node A, Node B){ return A.r<B.r; });
		for(int i=0;i<=n+1;i++) fa[i]=i, col[i]=0;
		tp = 0;
		int pt = 0, mv = 0;
		for(int i=1;i<=n;i++){
			if(id[s[i]] > 0){
				stk[++tp] = i;
				hsh[tp] = ((__int128)hsh[tp-1] * base + p[s[i]]) % mod;
			}else{
				if(!tp || !match(stk[tp], i)){
					tp = 0;
					pt = i;
				}else{
					color(stk[tp]+1, i-1);
					tp--;
				}
			}
			while(mv<m && t[mv+1].r==i){
				++mv;
				if(t[mv].l <= pt || col[t[mv].l]){
					lft[t[mv].id] = -1;
				}else{
					int L=1, R=tp, ans=0;
					while(L<=R){
						int mid=(L+R)>>1;
						if(stk[mid]<t[mv].l){
							ans=mid;
							L=mid+1;
						}else R=mid-1;
					}
					lft[t[mv].id] = gethash(ans+1, tp);

					// cout<<"id = "<<t[mv].id<<" l = "<<t[mv].id<<" pt = "<<pt<<endl;
					// printf("id = %d\n", t[mv].id);
					// for(int i=ans+1; i<=tp; i++)
					// 	printf("%c", s[stk[i]]);
					// puts("");
					// cout<<endl;
				}
			}
			// printf("r = %d\n", i);
			// for(int i=1;i<=tp;i++) putchar(s[stk[i]]); puts("");
		}
	}

	reverse(s+1, s+n+1);
	for(int i=1;i<=m;i++){
		t[i].l=n-t[i].l+1, t[i].r=n-t[i].r+1;
		swap(t[i].l, t[i].r);
	}

	// cout<<"-----------------\n";
	{
		sort(t+1, t+m+1, [](Node A, Node B){ return A.r<B.r; });
		for(int i=0;i<=n+1;i++) fa[i]=i, col[i]=0;
		tp = 0;
		int pt = 0, mv = 0;
		for(int i=1;i<=n;i++){
			if(id[s[i]] < 0){
				stk[++tp] = i;
				hsh[tp] = ((__int128)hsh[tp-1] * base + p[s[i]]) % mod;
			}else{
				if(!tp || !match(stk[tp], i)){
					tp = 0;
					pt = i;
				}else{
					color(stk[tp]+1, i-1);
					tp--;
				}
			}
			while(mv<m && t[mv+1].r==i){
				++mv;
				if(t[mv].l <= pt || col[t[mv].l]){
					rht[t[mv].id] = -1;
				}else{
					int L=1, R=tp, ans=0;
					while(L<=R){
						int mid=(L+R)>>1;
						if(stk[mid]<t[mv].l){
							ans=mid;
							L=mid+1;
						}else R=mid-1;
					}
					rht[t[mv].id] = gethash(ans+1, tp);
					// puts("-----");
					// printf("id = %d\n", t[mv].id);
					// for(int i=ans+1; i<=tp; i++)
					// 	printf("%c", s[stk[i]]);
					// puts("");
					// puts("-----");
				}
			}
			// printf("r = %d\n", i);
			// for(int i=1;i<=tp;i++) putchar(s[stk[i]]); puts("");
		}
	}
	int ans = 0;
	for(int i=1;i<=m;i++){
		// cout<<lft[i]<<" "<<rht[i]<<endl;
		if(lft[i] == 0 && rht[i] == 0) ans ++;
		else if(~lft[i]){
			mp1[lft[i]] ++;
		}else if(~rht[i]){
			mp2[rht[i]] ++;
		}
	}
	ans >>= 1;
	for(auto [p, q]: mp1){
		ans += min(q, mp2[p]);
	}

	printf("%d\n", ans);
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=read();
	id['['] = 1; id[']'] = -1;
	id['{'] = 2; id['}'] = -2;
	id['('] = 3; id[')'] = -3;
	id['<'] = 4; id['>'] = -4;

	pw[0] = 1;
	for(int i=1;i<=500000;i++) pw[i]=(__int128)pw[i-1]*base%mod;
	for(int i=0;i<255;i++)
		p[i] = (id[i]<0?-id[i]:id[i]);
	while(T--) procedure();
	return 0;
}