#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=N*4+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,X[N],Y[N];
char s[N],c[N];
map<ll,int> f1,f2;
int cnt=0;
int st[N],sh,to[N];
int g1[N][21],g2[N][21],d[N];
const ll P=ll(1e18)+7,bas=19260817;
using LL=__int128;
ll pw[N],sum[N];
void work(map<ll,int> &f){
	copy(s+1,s+n+1,c+1);
	sh=0;
	for(int i=n;i;i--){
		if(c[i]&1) st[++sh]=i,to[i]=i+1;
		else{
			if(c[i]==(c[st[sh]]^1)) to[i]=st[sh]+1,sh--;
			else to[i]=n+2,c[st[sh]]=0;
		}
	}
	for(int i=0;i<=20;i++) g1[n+1][i]=n+1,g1[n+2][i]=n+2;
	for(int i=n;i;i--){
		if(s[i]&1) for(int j=0;j<=20;j++) g1[i][j]=i;
		else{
			g1[i][0]=to[i];
			for(int j=1;j<=20;j++) g1[i][j]=g1[g1[i][j-1]][j-1];
		}
	}
	for(int i=0;i<=20;i++) g2[n+1][i]=n+1,g2[n+2][i]=n+2;
	for(int i=n;i;i--){
		g2[i][0]=to[i];
		for(int j=1;j<=20;j++) g2[i][j]=g2[g2[i][j-1]][j-1];
	}
	sum[n+1]=sum[n+2]=0;d[n+1]=d[n+2]=0;
	for(int i=n;i;i--){
		if(s[i]&1) sum[i]=(LL(sum[to[i]])*bas+s[i])%P,d[i]=d[to[i]]+1;
		else sum[i]=sum[to[i]],d[i]=d[to[i]];
	}
	for(int i=pw[0]=1;i<=n;i++) pw[i]=LL(pw[i-1])*bas%P;
	for(int i=1;i<=m;i++){
		int l=X[i],r=Y[i]+1;
		for(int j=20;~j;j--) if(g1[l][j]<=r) l=g1[l][j];
		if(l==r){cnt++;continue;}
		if(~s[l]&1) continue;
		int v=l;
		for(int j=20;~j;j--) if(g2[l][j]<=r) l=g2[l][j];
		// if(i==1) gdb(l,r,int(s[l]),to[19]);
		if(l^r) continue;
		f[(sum[v]+LL(P-sum[l])*pw[d[v]-d[l]])%P]++;
	}
}
void Solve(){
	scanf("%d%d",&n,&m);
	f1.clear();f2.clear();cnt=0;
	scanf("%s",s+1);
	for(int i=1;i<=m;i++) scanf("%d%d",&X[i],&Y[i]);
	// gdb(int('{'),int('}'),int('('),int(')'),int('['),int(']'),int('<'),int('>'));
	for(int i=1;i<=n;i++) if(s[i]=='>') s[i]--;
	for(int i=1;i<=n;i++) if(s[i]=='{'||s[i]=='[') s[i]++;
	work(f1);
	reverse(s+1,s+n+1);
	for(int i=1;i<=m;i++) X[i]=n-X[i]+1,Y[i]=n-Y[i]+1,swap(X[i],Y[i]);
	for(int i=1;i<=n;i++) s[i]^=1;
	work(f2);
	cnt>>=1;
	int ans=0;
	for(auto &[a,b]:f1) while(f2[a]&&b) f2[a]--,b--,ans++;
	ans+=cnt/2;
	printf("%d\n",ans);
}
int main(){
	int t=1;
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}