PROBLEM LINK:
Author: Adarsh Kumar Sinha
DIFFICULTY:
Easy
SOLUTION:
Setter's Solution
/*----- || Hare Krishna || -----*/
/* "WHY DO WE FALL, BRUCE?" */
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define elif else if
#define pb push_back
#define pf push_front
#define PI 3.1415926535897932384
#define MOD 1000000007
using namespace std;
char alpha[26] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
string s;
int t;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
cin >> t;
while(t--){
int n;
cin >> n;
cin >> s; // taking input sequence as a string
if(n&1){
cout << 0 << endl; // if n is odd, it is not possible
}
else{
int open,close; // number of opening brace, closing brace
open=close=0;
for(int i=0; i<n; i++){
if(s[i]=='('){
open++;
}
else{
if(open!=0){
open--;
}
else{
close++;
}
}
}
if((open==0 && close==0) || (open==2 && close==0) || (close==2 && open==0) ) { // if there was no open or close brace reamining (i.e, each brace got paired)
// ,or if there
// are exactly 2 open brace and 0 close brace, or 2 close brace
// and 0 open brace, only then it is POSSIBLE.
cout << 1 << endl;
}
else{
cout << 0 << endl;
}
}
}
}