#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back

pair <char, int> pci;
typedef unsigned long long ull;
template <class T>
inline void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	x = x * f;
}

const int MAXN = 5e5;
const ull P = 131;
ull h[MAXN + 10];
char s[MAXN + 10];

inline int ty(char c) {
	if (c == '(' || c == '[' || c == '{' || c == '<') return 0;
	return 1;
}

inline int chk(int l, int r) {
	if (s[l] == '(' && s[r] == ')') return 1;
	if (s[l] == '[' && s[r] == ']') return 1;
	if (s[l] == '{' && s[r] == '}') return 1;
	if (s[l] == '<' && s[r] == '>') return 1;
	return 0;
	//return s[r] - s[l] == 1;
}

int turn(int l) {
	if (s[l] == '(') return ')';
	if (s[l] == '[') return ']';
	if (s[l] == '{') return '}';
	if (s[l] == '<') return '>';
	assert(0);
	return 0;
}

struct SEG {
	int mn[MAXN * 4 + 10], mx[MAXN * 4 + 10];
	void pushup(int s) {
		mn[s] = min(mn[s << 1], mn[s << 1| 1]);
		mx[s] = max(mx[s << 1], mx[s << 1| 1]);
	}
	void upd(int l, int r, int x, int s, int v) {
		if (l == r) {
			mn[s] = v;
			mx[s] = v;
			return;
		}
		int mid = l + r >> 1;
		if (x <= mid) upd(l, mid, x, s << 1, v);
		else upd(mid + 1, r, x, s << 1 | 1, v);
		pushup(s);
	}
	int qmx(int l, int r, int L, int R, int s) {
		if (l > R || r < L) return 0;
		if (L <= l && r <= R)
			return mx[s];
		int mid = l + r >> 1;
		return max(qmx(l, mid, L, R, s << 1), qmx(mid + 1, r, L, R, s << 1 | 1));
	}

	int qmn(int l, int r, int L, int R, int s) {
		if (l > R || r < L) return MAXN + 10;
		if (L <= l && r <= R)
			return mn[s];
		int mid = l + r >> 1;
		return min(qmn(l, mid, L, R, s << 1), qmn(mid + 1, r, L, R, s << 1 | 1));
	}
	void build(int l, int r, int s) {
		if (l == r) {
			mn[s] = MAXN + 10;
			mx[s] = 0;
			return;
		}
		int mid = l + r >> 1;
		build(l, mid, s << 1);
		build(mid + 1, r, s << 1 | 1);
		pushup(s);
	}
}seg;

vector <int> v1[MAXN + 10], v2[MAXN + 10];
int sta[MAXN + 10], lm[MAXN + 10], rm[MAXN + 10];
ull pw[MAXN + 10];
unordered_map<ull, int> mp;

int main() {
	//freopen ("std.in", "r", stdin);
	//freopen ("std.out", "w", stdout);
	int T; read(T);
	while (T--) {
		int n, m;
		read(n); read(m);
		scanf("%s", s + 1);
		pw[0] = 1;
		for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * P;
		int top = 0, ans = 0;
		for (int i = 1; i <= m; ++i) {
			int l, r;
			read(l); read(r);
			//		cout << l << " " << r << endl;
			v1[r].pb(l);
			v2[l].pb(r);
		}
		seg.build(1, n, 1);
	//	cout << chk(3, 4) << endl;
		for (int i = 1; i <= n; ++i) {
			if (ty(s[i])) {
				if (top && chk(sta[top], i)) {
					lm[i] = sta[top];
					--top;
				}
				else
					lm[i] = top = 0;
				seg.upd(1, n, i, 1, lm[i]);
				//			cout << i << " " << lm[i] << endl;
			}
			else {
				sta[++top] = i;
				h[top] = h[top - 1] * P + turn(i);
			}
			for (auto v : v1[i]) {
				int mn = seg.qmn(1, n, v, i, 1);
				if (mn >= v) {
					int p = lower_bound(sta + 1, sta + top + 1, v) - sta;
					ull val = h[top] - h[p - 1] * pw[top - p + 1];
				//	cout << v << " " << i << " " << val << endl;
					++mp[val];
				}
			}
		}
	//	cout << endl;
		top = 0;
		seg.build(1, n, 1);
		for (int i = 1; i <= n; ++i) rm[i] = n + 1;
		for (int i = n; i >= 1; --i) {
			if (!ty(s[i])) {
				if (top && chk(i, sta[top])) {
					rm[i] = sta[top];
					--top;
				}
				else {
					rm[i] = n + 1;
					top = 0;
				}
				seg.upd(1, n, i, 1, rm[i]);
			}
			else {
				sta[++top] = i;
				h[top] = h[top - 1] * P + s[i];
			}
			for (auto v : v2[i]) {
				int mx = seg.qmx(1, n, i, v, 1);
				if (mx <= v) {
					int p = lower_bound(sta + 1, sta + top + 1, v, greater<int>()) - sta;
					ull val = h[top] - h[p - 1] * pw[top - p + 1];
			//		cout << i << " " << v << " " << val << endl;
					if (!val) ++mp[val];
					else {
						auto t = mp.find(val);
						if (t != mp.end() && mp[val] > 0) {
							--mp[val];
							++ans;
						}
					}
				}
			}
		}
		assert(mp[0] % 2 == 0);
	//	cout << ans << endl;
		ans += mp[0] / 2 / 2;
		printf("%d\n", ans);
		for (int i = 1; i <= n; ++i) {
			v1[i].clear();
			v2[i].clear();
		}
		unordered_map <ull, int> ().swap(mp);
	}
	return 0;
}