#include<cstdio>
#include<algorithm>
#define N 500010
#define BASE 233
int n, m;
struct wy{
	int l, r;
	int type;
	unsigned long long hash;
};
char a[N], s[N];
int top, pos[N];
wy t[N];
unsigned long long hash[N], power[N];

inline void pre(){
	power[0] = 1;
	for(int i = 1; i < N; i++){
		power[i] = power[i-1] * BASE;
	}
}
inline unsigned long long getHash(int l, int r){
	return hash[r] - hash[l-1] * power[r-l+1];
}

int ill[N];
inline int findPos(int x, int lim){
	if(x < lim || ill[x]){
		return -1;
	}
	if(x > pos[top]){
		return top + 1;
	}
	int l = 1, r = top, mid, ans = -1;
	while(l <= r){
		mid = (l + r) >> 1;
		if(x <= pos[mid]){
			ans = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	return ans;
}
int set[N];
inline int find(int k){
	return set[k] == k ? k : set[k] = find(set[k]);
}
inline void makeIll(int l, int r){
	for(int i = l, next; i <= r; i = next){
		ill[i] = 1;
		next = find(i) + 1;
		set[i] = find(r);
	}
}
inline char trans(char a){
	if(a == '(') a = ')';
	else if(a == ')') a = '(';
	else if(a == '[') a = ']';
	else if(a == ']') a = '[';
	else if(a == '{') a = '}';
	else if(a == '}') a = '{';
	else if(a == '<') a = '>';
	else if(a == '>') a = '<';
	return a;
}
inline void deal(int type){
	std::sort(t + 1, t + 1 + m, [](const wy &a, const wy &b){
		return a.r < b.r;
	});
	top = 0;
	for(int i = 1; i <= n; i++){
		set[i] = i;
		ill[i] = 0;
	}
	int lim = 1;
	for(int i = 1, j = 1; i <= n; i++){
		if(a[i] == ')' || a[i] == '}' || a[i] == '>' || a[i] == ']'){
			if(top == 0 || s[top] != a[i]){
				top = 0;
				lim = i + 1;
			}
			else{
				makeIll(pos[top] + 1, i);
//					printf("ill: %d %d\n", pos[top] + 1, i);
				top--;
			}
		}
		else{
			s[++top] = trans(a[i]);
			pos[top] = i;
			hash[top] = hash[top - 1] * BASE + a[i];
		}
		while(t[j].r == i && j <= m){
			int l = findPos(t[j].l, lim);
			if(l == top + 1){
				t[j].type = 3;
			}
			else if(l != -1){
				t[j].type = type;
				t[j].hash = getHash(l, top);
			}
			j++;
		}
	}
}
unsigned long long hash1[N], hash2[N];
int main(){
	pre();
	int T;
	scanf("%d", &T);
	int id = 0;
	while(T--){
		scanf("%d%d", &n, &m);
		scanf("%s", a + 1);
		for(int  i = 1; i <= m; i++){
			scanf("%d%d", &t[i].l, &t[i].r);
			t[i].hash = t[i].type = 0; 
		}
		
		deal(1);
		
		for(int  i = 1; i <= n; i++){
			a[i] = trans(a[i]);
		}
		for(int i = 1, j = n; i < j; i++, j--){
			std::swap(a[i], a[j]);
		}
		for(int i = 1; i <= m; i++){
			t[i].l = n - t[i].l + 1;
			t[i].r = n - t[i].r + 1;
			std::swap(t[i].l, t[i].r);
		}
		deal(2);
		
		int ans = 0;
		int type3 = 0, type1 = 0, type2 = 0;
		for(int i = 1; i <= m; i++){
	//			printf(">>> %d %d %d %llu\n", t[i].l ,t[i].r, t[i].type, t[i].hash);
			if(t[i].type == 3){
				type3++;
			}
			else if(t[i].type == 1){
				hash1[++type1] = t[i].hash;
			}
			else if(t[i].type == 2){
				hash2[++type2] = t[i].hash;
			}
		}
		
		ans = type3 >> 1;
		
		std::sort(hash1 + 1, hash1 + 1 + type1);
		std::sort(hash2 + 1, hash2 + 1 + type2);
		for(int i = 1, j = 1; i <= type1 && j <= type2;){
			if(hash1[i] == hash2[j]){
				ans++;
				i++;
				j++;
			}
			else if(hash1[i] < hash2[j]){
				i++;
			}
			else{
				j++;
			}
		}
		
		printf("%d\n", ans);
		
//		if(++id == 3 && ans == 2){
//			printf("%s\n", a + 1);
//			for(int i = 1; i <= 25; i++){
//				printf("%d %d\n", t[i].l, t[i].r);
//			}
//			puts("");
//		}
	}
	return 0;
}