// Author: YE Minghan
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "templates/debug.h"
#define __int128 ll
#else
#define dbg(...) (void)0
#define msg(...) (void)0
#endif
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

#define ull unsigned ll
const int N=500005;
const ull B=549499;
ull P[N];
const string LEFT=" ([{<",RIGHT=" )]}>";
int n,m,a[N];
map<ull,PII>fs;
int empt;
VI ls[N],rs[N];
int bk[N];

int _F(char c){int t=LEFT.find(c);return ~t?t:-RIGHT.find(c);}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
	
	P[0]=1;for(int i=1;i<N;i++)P[i]=P[i-1]*B;
	int _;cin>>_;while(_--)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){char c;cin>>c;a[i]=_F(c);}
	a[n+1]=empt=0;
	for(int i=1,l,r;i<=m;i++)cin>>l>>r,ls[r].PB(l),rs[l].PB(r);
	vector<pair<int,ull>>stk;
	stk.PB(0,0);
	for(int i=1,lst=0;i<=n;i++)
	{
		if(a[i]>0)stk.PB(i,stk.back().se*B+a[i]);
		else
		{
			if(a[stk.back().fi]!=-a[i])stk.clear(),stk.PB(0,0),lst=i;
			else stk.PPB();
		}
		for(int l:ls[i])
		{
			if(l<=lst)continue;
			auto it=lower_bound(ALL(stk),MP(l,0ull));
			if((it-1)->fi==bk[l-1])
			{
				if(it==stk.end())empt++;
				else fs[stk.back().se-(it-1)->se*P[stk.end()-it]].fi++;
			}
		}
		bk[i]=stk.back().fi;
	}
	stk.clear(),stk.PB(n+1,0),bk[n+1]=n+1;
	for(int i=n,lst=n+1;i;i--)
	{
		if(a[i]<0)stk.PB(i,stk.back().se*B-a[i]);
		else
		{
			if(a[stk.back().fi]!=-a[i])stk.clear(),stk.PB(n+1,0),lst=i;
			else stk.PPB();
		}
		for(int r:rs[i])
		{
			if(r>=lst)continue;
			auto it=lower_bound(ALL(stk),MP(r,-1ull),greater<>());
			if((it-1)->fi==bk[r+1])
			{
				if(it==stk.end())empt++;
				else fs[stk.back().se-(it-1)->se*P[stk.end()-it]].se++;
			}
		}
		bk[i]=stk.back().fi;
	}
	int ans=empt>>2;
	for(auto [v,p]:fs)ans+=min(p.fi,p.se);
	cout<<ans<<endl;

	fs.clear();
	for(int i=1;i<=n;i++)ls[i].clear(),rs[i].clear();
}

	return 0;
}