#include <bits/stdc++.h>
using namespace std;
string s;
int check(int l, int r, int depth) {
if (l > r) return 0;
if (l == r - 1) return 1;
stack<pair<int, int>> stk;
int ans = 1;
for (int i = l; i <= r; i++) {
if (s[i] == '(') {
stk.push({i, depth + stk.size()});
} else {
pair<int, int> p = stk.top();
stk.pop();
if (p.second == depth) {
ans += check(p.first + 1, i - 1, depth + 1);
}
}
}
return ans;
}
void solve() {
int n;
cin >> n;
cin >> s;
cout << check(0, 2 * n - 1, 1) << endl;
}
int main() {
// your code goes here
int t;
cin >> t;
while (t--) solve();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJpbmcgczsKCmludCBjaGVjayhpbnQgbCwgaW50IHIsIGludCBkZXB0aCkgewoJaWYgKGwgPiByKSByZXR1cm4gMDsKCWlmIChsID09IHIgLSAxKSByZXR1cm4gMTsKCXN0YWNrPHBhaXI8aW50LCBpbnQ+PiBzdGs7CglpbnQgYW5zID0gMTsKCWZvciAoaW50IGkgPSBsOyBpIDw9IHI7IGkrKykgewoJCWlmIChzW2ldID09ICcoJykgewoJCQlzdGsucHVzaCh7aSwgZGVwdGggKyBzdGsuc2l6ZSgpfSk7CgkJfSBlbHNlIHsKCQkJcGFpcjxpbnQsIGludD4gcCA9IHN0ay50b3AoKTsKCQkJc3RrLnBvcCgpOwoJCQlpZiAocC5zZWNvbmQgPT0gZGVwdGgpIHsKCQkJCWFucyArPSBjaGVjayhwLmZpcnN0ICsgMSwgaSAtIDEsIGRlcHRoICsgMSk7CgkJCX0KCQl9Cgl9CglyZXR1cm4gYW5zOwp9Cgp2b2lkIHNvbHZlKCkgewoJaW50IG47CgljaW4gPj4gbjsKCWNpbiA+PiBzOwoJY291dCA8PCBjaGVjaygwLCAyICogbiAtIDEsIDEpIDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW50IHQ7CgljaW4gPj4gdDsKCXdoaWxlICh0LS0pIHNvbHZlKCk7Cn0=