#include <cstdio>
#include <algorithm>
#define ls p << 1
#define rs p << 1 | 1

int tab[1005];
using std::min; using std::max;
const int mod = 998244353, seed = 233;
inline int plus(const int x, const int y) {return x + y < mod ? x + y : x + y - mod;}
inline int sub(const int x, const int y) {return x >= y ? x - y : x - y + mod;}
int id[55], st[55], ed[55], b[55], top, n, m, cnt;
char s[500005];
int ps[500005], is[500005], full[500005];
struct str {
	int len, h1, h2;
	str operator + (const str &rhs) const {
		return str{len + rhs.len, (1ll * h1 * ps[rhs.len] + rhs.h1) % mod,
		(h2 + 1ll * ps[len] * rhs.h2) % mod};
	}
	str delback(const str &rhs) const {
		return str{len - rhs.len, 1ll * sub(h1, rhs.h1) * is[rhs.len] % mod,
		sub((h2 - 1ll * rhs.h2 * ps[len - rhs.len]) % mod, 0)};
	}
	str delfront(const str &rhs) const {
		return str{len - rhs.len, sub((h1 - 1ll * rhs.h1 * ps[len - rhs.len]) % mod, 0),
		1ll * sub(h2, rhs.h2) * is[rhs.len] % mod};
	}
	str rev() const {return str{len, sub(full[len], h2), sub(full[len], h1)};}
	inline bool operator == (const str &rhs) const {
		return len == rhs.len && h1 == rhs.h1 && h2 == rhs.h2;
	}
	inline bool operator < (const str &rhs) const {
		return len ^ rhs.len ? len < rhs.len : (h1 ^ rhs.h1 ? h1 < rhs.h1 : h2 < rhs.h2);
	}
};
struct String {
	str s1, s2; bool rev;
	inline bool operator < (const String &rhs) const {
		return s1 == rhs.s1 ? s2 < rhs.s2 : s1 < rhs.s1;
	}
} a[500005];
struct node {int l, r, lft, rgt; str v, del;} tr[2000005];
str calc1(int p, int x) {
	if (!x) return str{0, 0, 0};
	if (x == tr[p].v.len) return tr[p].v;
	int mid = tr[ls].v.len - tr[p].del.len;
	return x <= mid ? calc1(ls, x) : tr[ls].v.delback(tr[p].del) +
	calc1(rs, x - mid + tr[p].del.len).delfront(tr[p].del.rev());
}
str calc(int p, int l, int r) {
	if (l > r) return str{0, 0, 0};
	if (l == 1 && r == tr[p].v.len) return tr[p].v;
	return calc1(p, r).delfront(calc1(p, l - 1));
}
void build(int p, int l, int r) {
	tr[p].l = l, tr[p].r = r;
	if (l < r) {
		build(ls, l, l + r >> 1), build(rs, (l + r >> 1) + 1, r), tr[p].del = str{0, 0, 0};
		if (tr[ls].lft == -1 || tr[rs].lft == -1) {tr[p].lft = -1; return;}
		int tmp = min(tr[ls].lft, tr[rs].rgt);
		tr[p].del = calc(ls, tr[ls].v.len - tmp + 1, tr[ls].v.len);
		if (!(tr[p].del == calc(rs, 1, tmp).rev())) {tr[p].lft = -1; return;}
		tr[p].v = tr[ls].v.delback(tr[p].del) + tr[rs].v.delfront(tr[p].del.rev());
		tr[p].rgt = tr[ls].rgt + tr[rs].rgt - tmp, tr[p].lft = tr[ls].lft - tmp + tr[rs].lft;
	} else tr[p].v = str{1, tab[s[l]], tab[s[l]]}, tr[p].lft = tab[s[l]] <= 4,
	tr[p].rgt = tab[s[l]] > 4;
}
void getnode(int p, int l, int r) {
	if (l <= tr[p].l && tr[p].r <= r) {b[++ cnt] = p; return;}
	int mid = tr[p].l + tr[p].r >> 1;
	if (l <= mid) getnode(p << 1, l, r);
	if (mid < r) getnode(p << 1 | 1, l, r);
}
void meinkampf() {
	scanf("%d%d%s", &n, &m, s + 1);
	build(1, 1, n);
	int __ = 0;
	for (int _ = 1, l, r; _ <= m; ++ _) {
		scanf("%d%d", &l, &r), top = cnt = 0, getnode(1, l, r);
		bool flg = 1;
		for (int i = 1; i <= cnt; ++ i) flg &= tr[b[i]].lft != -1;
		if (!flg) continue;
		for (int i = 1; i <= cnt; ++ i) {
			int p = b[i], now = 0;
			while (top && now < tr[p].rgt) {
				int q = id[top], rmv = min(tr[p].rgt - now,
				max(0, tr[q].lft - (tr[q].v.len - ed[top])));
				if (!rmv || calc(p, now + 1, now + rmv).rev() ==
				calc(q, ed[top] - rmv + 1, ed[top])) {
					ed[top] -= rmv, now += rmv;
					if (st[top] > ed[top]) -- top; else break;
				} else {flg = 0; break;}
			}
			if (!flg) break;
			if (tr[p].lft || now < tr[p].rgt)
				id[++ top] = p, st[top] = now + 1, ed[top] = tr[p].v.len;
		}
		if (!flg || (top && st[1] <= tr[id[1]].rgt &&
		tr[id[top]].lft > tr[id[top]].v.len - ed[top])) continue;
		str ans = str{0, 0, 0};
		for (int i = 1; i <= top; ++ i) ans = ans + calc(id[i], st[i], ed[i]);
		if (ans < ans.rev()) a[++ __] = String{ans, ans.rev(), 0};
		else a[++ __] = String{ans.rev(), ans, 1};
	}
	std::sort(a + 1, a + __ + 1); int ans = 0;
	for (int i = 1; i <= __; ++ i) {
		int j = i, c0 = 0, c1 = 0; if (a[i].rev) ++ c1; else ++ c0;
		while (j < __ && a[i].s1 == a[j + 1].s1 && a[i].s2 == a[j + 1].s2)
			if (a[++ j].rev) ++ c1; else ++ c0;
		if (a[i].s1.len) ans += min(c0, c1);
		else ans += c0 + c1 >> 1;
		i = j;
	}
	printf("%d\n", ans);
}

int main() {
	tab['('] = 1, tab[')'] = 8, tab['['] = 2, tab[']'] = 7;
	tab['{'] = 3, tab['}'] = 6, tab['<'] = 4, tab['>'] = 5;
	for (int i = ps[0] = is[0] = 1; i <= 500000; ++ i)
		ps[i] = 1ll * ps[i - 1] * seed % mod, is[i] = 844009174ll * is[i - 1] % mod,
		full[i] = (1ll * full[i - 1] * seed + 9) % mod;
	int _; scanf("%d", &_); while (_ --) meinkampf();
	return 0;
}