#include<iostream>
#include<algorithm>
#include<array>
#include<vector>
#include<chrono>
#include<random>
#include<cassert>
using namespace std;
//https://nyaannyaan.github.io/library/internal/internal-hash.hpp

namespace internal{
using i64 = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;

template <int BASE_NUM = 2>
struct Hash : array<u64, BASE_NUM> {
  using array<u64, BASE_NUM>::operator[];
  static constexpr int n = BASE_NUM;

  Hash() : array<u64, BASE_NUM>() {}

  static constexpr u64 md = (1ull << 61) - 1;

  constexpr static Hash set(const i64 &a) {
    Hash res;
    fill(begin(res), end(res), cast(a));
    return res;
  }
  Hash &operator+=(const Hash &r) {
    for (int i = 0; i < n; i++)
      if (((*this)[i] += r[i]) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator+=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++)
      if (((*this)[i] += s) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator-=(const Hash &r) {
    for (int i = 0; i < n; i++)
      if (((*this)[i] += md - r[i]) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator-=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++)
      if (((*this)[i] += md - s) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator*=(const Hash &r) {
    for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], r[i]);
    return *this;
  }
  Hash &operator*=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], s);
    return *this;
  }

  Hash operator+(const Hash &r) { return Hash(*this) += r; }
  Hash operator+(const i64 &r) { return Hash(*this) += r; }
  Hash operator-(const Hash &r) { return Hash(*this) -= r; }
  Hash operator-(const i64 &r) { return Hash(*this) -= r; }
  Hash operator*(const Hash &r) { return Hash(*this) *= r; }
  Hash operator*(const i64 &r) { return Hash(*this) *= r; }
  Hash operator-() const {
    Hash res;
    for (int i = 0; i < n; i++) res[i] = (*this)[i] == 0 ? 0 : md - (*this)[i];
    return res;
  }
  friend Hash pfma(const Hash &a, const Hash &b, const Hash &c) {
    Hash res;
    for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], c[i]);
    return res;
  }
  friend Hash pfma(const Hash &a, const Hash &b, const i64 &c) {
    Hash res;
    u64 s = cast(c);
    for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], s);
    return res;
  }

  Hash pow(long long e) {
    Hash a{*this}, res{Hash::set(1)};
    for (; e; a *= a, e >>= 1) {
      if (e & 1) res *= a;
    }
    return res;
  }

  static Hash get_basis() {
    static auto rand_time =
        chrono::duration_cast<chrono::nanoseconds>(
            chrono::high_resolution_clock::now().time_since_epoch())
            .count();
    static mt19937_64 rng(rand_time);
    Hash h;
    for (int i = 0; i < n; i++) {
      while (isPrimitive(h[i] = rng() % (md - 1) + 1) == false)
        ;
    }
    return h;
  }

 private:
  static u64 modpow(u64 a, u64 b) {
    u64 r = 1;
    for (a %= md; b; a = modmul(a, a), b >>= 1) r = modmul(r, a);
    return r;
  }
  static bool isPrimitive(u64 x) {
    for (auto &d : vector<u64>{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321})
      if (modpow(x, (md - 1) / d) <= 1) return false;
    return true;
  }
  static inline constexpr u64 cast(const long long &a) {
    return a < 0 ? a + md : a;
  }
  static inline constexpr u64 modmul(const u64 &a, const u64 &b) {
    u128 d = u128(a) * b;
    u64 ret = (u64(d) & md) + u64(d >> 61);
    return ret >= md ? ret - md : ret;
  }
  static inline constexpr u64 modfma(const u64 &a, const u64 &b, const u64 &c) {
    u128 d = u128(a) * b + c;
    u64 ret = (d >> 61) + (u64(d) & md);
    return ret >= md ? ret - md : ret;
  }
};

}
/**
 * @brief 繝上ャ繧ｷ繝･讒矩€菴・ * @docs docs/internal/internal-hash.md
 */

using Hash=internal::Hash<2>;
Hash basis=Hash::get_basis();
Hash pw[5<<17];
int N,M;
pair<vector<pair<int,Hash> >,vector<pair<int,int> > >calc(vector<pair<int,bool> >SH,vector<vector<int> >RtoL)
{
	assert(SH.size()==N);
	assert(RtoL.size()==N+1);
	assert(RtoL[0].empty());
	vector<Hash>cur;
	vector<int>bra,idx;
	cur.push_back(Hash::set(0));
	bra.push_back(-1);
	idx.push_back(0);
	vector<int>depth(N+1);
	depth[0]=0;
	vector<pair<int,Hash> >L;
	vector<pair<int,int> >S;
	for(int r=1;r<=N;r++)
	{
		if(SH[r-1].second)
		{//close
			depth[r]=depth[r-1]-1;
			if(bra.back()==SH[r-1].first)
			{
				bra.pop_back();
				cur.pop_back();
				idx.pop_back();
			}
			else
			{
				bra.clear();
				cur.clear();
				idx.clear();
				cur.push_back(Hash::set(0));
				bra.push_back(-1);
				idx.push_back(r);
			}
		}
		else
		{//open
			depth[r]=depth[r-1]+1;
			bra.push_back(SH[r-1].first);
			cur.push_back(cur.back()*basis+Hash::set(SH[r-1].first));
			idx.push_back(r);
		}
		for(int l:RtoL[r])
		{
			if(depth[l]>depth[r])continue;
			if(depth[l]==depth[r])
			{
				if(idx.back()<=l)S.push_back(make_pair(l,r));
			}
			else
			{
				int d=depth[r]-depth[l];
				assert(d>=1);
				if(cur.size()<=d)continue;
				if(idx[idx.size()-d-1]<=l&&idx[idx.size()-d]>l)
				{
					L.push_back(make_pair(d,cur.back()-cur[cur.size()-d-1]*pw[d]));
				}
			}
		}
	}
	return make_pair(L,S);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	pw[0]=Hash::set(1);
	for(int i=1;i<5<<17;i++)pw[i]=pw[i-1]*basis;
	int T;cin>>T;
	for(;T--;)
	{
		string S;
		cin>>N>>M>>S;
		vector<pair<int,bool> >SH(N);
		for(int i=0;i<N;i++)
		{
			if(S[i]=='(')SH[i]=make_pair(1,false);
			else if(S[i]==')')SH[i]=make_pair(1,true);
			else if(S[i]=='[')SH[i]=make_pair(2,false);
			else if(S[i]==']')SH[i]=make_pair(2,true);
			else if(S[i]=='{')SH[i]=make_pair(3,false);
			else if(S[i]=='}')SH[i]=make_pair(3,true);
			else if(S[i]=='<')SH[i]=make_pair(4,false);
			else if(S[i]=='>')SH[i]=make_pair(4,true);
			else assert(false);
		}
		vector<vector<int> >LtoR(N+1),RtoL(N+1);
		for(int i=0;i<M;i++)
		{
			int l,r;cin>>l>>r;
			l--;
			LtoR[N-l].push_back(N-r);
			RtoL[r].push_back(l);
		}
		auto[L,SL]=calc(SH,RtoL);
		reverse(SH.begin(),SH.end());
		for(int i=0;i<N;i++)SH[i].second=!SH[i].second;
		auto[R,SR]=calc(SH,LtoR);
		sort(SL.begin(),SL.end());
		for(int i=0;i<SR.size();i++)
		{
			auto[l,r]=SR[i];
			SR[i]=make_pair(N-r,N-l);
		}
		sort(SR.begin(),SR.end());
		assert(SL==SR);
		int ans=SL.size()/2;
		{
			sort(L.begin(),L.end());
			sort(R.begin(),R.end());
			int li=0,ri=0;
			while(li<L.size()&&ri<R.size())
			{
				if(L[li]==R[ri])ans++,li++,ri++;
				else if(L[li]<R[ri])li++;
				else ri++;
			}
		}
		cout<<ans<<"\n";
	}
}