让我们从左到右遍历字符串 $s$ 的字符，同时维护当前的括号平衡数（对于位置 $i$，平衡数定义为前缀中直到第 $i$ 个字符的开括号数量减去闭括号数量）。

如果当前的平衡数变成负数，那么我们就从当前位置之后取一个开括号（显然它是存在的，因为开括号的总数等于闭括号的总数），并将其移动到字符串的开头（这样负数平衡就会重新变为 $0$，同时答案增加 $1$）。或者，我们也可以将当前的闭括号移动到字符串的末尾，因为这会导致相同的结果。

时间复杂度：$O(n)$。

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		string s;
		cin >> n >> s;
		int ans = 0;
		int bal = 0;
		for (int i = 0; i < n; ++i) {
			if (s[i] == '(') ++bal;
			else {
				--bal;
				if (bal < 0) {
					bal = 0;
					++ans;
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}