// created:  2024-12-07 11:20:04
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<chrono>
#include<random>
#include<vector>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned long long ull;
constexpr int N=5e5+5,MOD=965737163;
constexpr char bc[]="()<>[]{}";
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int bas[N][4];
struct hash_value
{
	int len,v[4];
	void init(int a,int b)
	{
		len=a;
		F(i,0,4)v[i]=b;
	}
	friend hash_value operator*(const hash_value &u,const hash_value &v)
	{
		if(!~u.len||!~v.len)return {-1,{0,0,0,0}};
		hash_value w=v;
		w.len+=u.len;
		F(i,0,4)w.v[i]=(int)((w.v[i]+(ull)u.v[i]*bas[v.len][i])%MOD);
		return w;
	}
	friend bool operator<(const hash_value &u,const hash_value &v){return memcmp(&u,&v,sizeof(hash_value))<0;}
	friend bool operator==(const hash_value &u,const hash_value &v){return !memcmp(&u,&v,sizeof(hash_value));}
};
struct elem
{
	hash_value a;
	elem(){}
	elem(hash_value a_):a(a_){}
	elem(int x)
	{
		if(x==-1)a.init(0,0);
		else if(x&1)a.init(-1,0);
		else a.init(1,x>>1);
	}
	friend elem operator*(const elem &a,const elem &b){return elem{a.a*b.a};}
};
namespace seg
{
	constexpr int N=(1<<20)+5;
	elem s[N];
#define lc (p<<1)
#define rc (p<<1|1)
	void build(int p,int l,int r)
	{
		s[p]=-1;
		if(r-l==1)return;
		int mid=(l+r)>>1;
		build(lc,l,mid);build(rc,mid,r);
	}
	void update(int p,int l,int r,int x,int y)
	{
		if(r-l==1)return s[p]=y,void();
		int mid=(l+r)>>1;
		if(x<mid)update(lc,l,mid,x,y);
		else update(rc,mid,r,x,y);
		s[p]=s[lc]*s[rc];
	}
	elem query(int p,int l,int r,int x)
	{
		if(x==l)return s[p];
		int mid=(l+r)>>1;
		if(x>=mid)return query(rc,mid,r,x);
		return query(lc,l,mid,x)*s[rc];
	}
#undef lc
#undef rc
}
int n,m,sta[N],top,p[N];
char s[N];
vector<int> le[N],ri[N];
vector<hash_value> va,vb;
void solve()
{
	read(n,m);
	scanf("%s",s);
	F(i,0,n)s[i]=(char)(lower_bound(bc,bc+8,s[i])-bc),p[i+1]=p[i]+(s[i]&1?-1:1);
	F(i,0,n+1)le[i].clear(),ri[i].clear();
	F(i,0,m)
	{
		int l,r;read(l,r);--l;
		le[r].emplace_back(l);
		ri[l].emplace_back(r);
	}
	int zero=0;
	va.clear();vb.clear();
	seg::build(1,0,n);
	F(i,0,n)
	{
		if((s[i]&1)&&top&&s[sta[top-1]]==s[i]-1)seg::update(1,0,n,sta[--top],-1);
		else seg::update(1,0,n,sta[top++]=i,s[i]);
		for(int j:le[i+1])
		{
			elem a=seg::query(1,0,n,j);
			if(!a.a.len&&p[i+1]==p[j])++zero;
			else if(~a.a.len&&a.a.len==p[i+1]-p[j])va.emplace_back(a.a);
		}
	}
	seg::build(1,0,n);
	top=0;
	F(i,0,n)s[i]^=1;
	for(int i=n;~--i;)
	{
		if((s[i]&1)&&top&&s[sta[top-1]]==s[i]-1)seg::update(1,0,n,n-1-(sta[--top]),-1);
		else seg::update(1,0,n,n-1-(sta[top++]=i),s[i]);
		for(int j:ri[i])
		{
			elem a=seg::query(1,0,n,n-j);
			if(a.a.len>0&&a.a.len==p[i]-p[j])vb.emplace_back(a.a);
		}
	}
	int ans=zero>>1;
	sort(va.begin(),va.end());
	sort(vb.begin(),vb.end());
	vector<hash_value>::iterator i=va.begin(),j=vb.begin();
	while(i<va.end()&&j<vb.end())
	{
		if(*i==*j)++i,++j,++ans;
		else if(*i<*j)++i;
		else ++j;
	}
	printf("%d\n",ans);
}
int main()
{
	F(i,0,4)
	{
		bas[0][i]=1;
		bas[1][i]=(int)(rnd()%(MOD-100)+50);
	}
	F(i,2,N)F(j,0,4)bas[i][j]=(int)((ull)bas[i-1][j]*bas[1][j]%MOD);
	int tt;read(tt);
	while(tt--)solve();
	return 0;
}