#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
const ll inf=LLONG_MAX/4;
#define rep2(i,j,k) for(ll i=ll(j);i<ll(k);i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i,k) rrep2(i,k,0)
#define eb emplace_back
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
template<class T>
bool chmin(T& a, T b){return a>b ? a=b,1:0;}
template<class T>
bool chmax(T& a, T b){return a<b ? a=b,1:0;}

using u64 = uint64_t;
const u64 mod = inf;
u64 add(u64 a, u64 b) {
	a += b;
	if(a >= mod) a -= mod;
	return a;
}

u64 mul(u64 a, u64 b) {
	auto c = (__uint128_t)a * b;
	return add(c >> 61, c & mod);
}
random_device rnd;
const u64 R = ((u64)rnd() << 32 | rnd()) % mod;

const int C = 1000000;
u64 pw[C];

P f(char c) {
	if(c == '(') return {0, 0};
	if(c == ')') return {0, 1};
	if(c == '[') return {1, 0};
	if(c == ']') return {1, 1};
	if(c == '{') return {2, 0};
	if(c == '}') return {2, 1};
	if(c == '<') return {3, 0};
	if(c == '>') return {3, 1};
	assert(false);
}

class Segtree {
	using S = ll;
	const S e = inf;
	S op(S a, S b) { return min(a, b); }

	int n;
	vector<S> d;

	void update(int k) {
		d[k] = op(d[2*k], d[2*k+1]);
	}

public:
	Segtree(const vector<S> &init) {
		n = 1;
		while(n < SZ(init)) n *= 2;
		d.assign(2*n, e);
		rep(i, SZ(init)) d[n+i] = init[i];
		rrep2(i, n, 1) update(i);
	}

	S prod(int l, int r) {
		assert(0 <= l and l <= r and r <= n);
		l += n, r += n;
		S res = e;
		while(l < r) {
			if(l&1) res = op(res, d[l++]);
			if(r&1) res = op(res, d[--r]);
			l >>= 1;
			r >>= 1;
		}
		return res;
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	vl ht(n+1);
	rep(i, n) ht[i+1] = ht[i] + (f(s[i]).second ? -1 : 1);
	Segtree st(ht);
	vl l(m), r(m), tp(m);
	rep(i, m) {
		cin >> l[i] >> r[i];
		--l[i];
		int mn = st.prod(l[i], r[i]+1);
		if(mn < min(ht[l[i]], ht[r[i]])) {
			tp[i] = -1;
		} else {
			tp[i] = (ht[l[i]] <= ht[r[i]] ? 0 : 1);
		}
	}
	map<u64, P> mp;
	ll comp = 0;
	rep(p, 2) {
		vp par(1);
		vvl G(1);
		par[0] = {-1, -1};
		int sz = 1, now = 0;
		vl fr(n), to(n);
		rep(i, n) {
			auto [t, c] = f(s[i]);
			c ^= p;
			if(c) {
				if(par[now].second == t) {
					fr[i] = now;
					to[i] = par[now].first;
					now = to[i];
				} else {
					fr[i] = to[i] = -1;
					par.eb(-1, -1);
					G.eb();
					sz += 1;
					now = sz-1;
				}
			} else {
				fr[i] = now;
				to[i] = sz;
				par.eb(now, t);
				G[now].eb(sz);
				G.eb();
				++sz;
				now = sz-1;
			}
		}
		vl in(sz, -1), out(sz), dep(sz);
		vector<u64> hs(sz);
		int k = 0;
		auto dfs = [&](auto &dfs, int u, int p, int d, u64 h) -> void {
			in[u] = k++;
			dep[u] = d;
			hs[u] = h;
			for(auto v : G[u]) {
				if(v == p) continue;
				u64 nh = add(mul(h, R), par[v].second+1);
				dfs(dfs, v, u, d+1, nh);
			}
			out[u] = k;
		};
		rep(i, sz) if(in[i] == -1) dfs(dfs, i, -1, 0, 0);
		rep(i, m) {
			if(tp[i] != p) continue;
			int FR = fr[l[i]];
			int TO = to[r[i]-1];
			if(FR == -1 or TO == -1 or in[FR] > in[TO] or out[FR] <= in[TO]) continue;
			u64 h = add(hs[TO], mod-mul(hs[FR], pw[dep[TO] - dep[FR]]));
			assert(ht[l[i]] <= ht[r[i]]);
			if(ht[l[i]] == ht[r[i]]) ++comp;
			else if(!p) ++mp[h].first;
			else ++mp[h].second;
		}
		reverse(all(s));
		reverse(all(ht));
		rep(i, m) {
			l[i] = n-l[i];
			r[i] = n-r[i];
			swap(l[i], r[i]);
		}
	}
	int ans = comp / 2;
	for(auto [_, p]: mp) ans += min(p.first, p.second);
	cout << ans << '\n';
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	pw[0] = 1;
	rep(i, C-1) pw[i+1] = mul(pw[i], R);
	int t;
	cin >> t;
	rep(_, t) solve();
}