#include<fstream>
using namespace std;
ifstream cin ("paranteze1.in");
ofstream cout("paranteze1.out");
struct stiva
{int v[1002],varf;
};
int suma(char s[260])
{int sum=0;
    for(int i=0;i<strlen(s);i++)
{if(s[i]=='(')
    sum=sum+1;
    else if(s[i]==')')
        sum=sum-1;
}
 return sum;
}
int main()
{char s[260];
    int n,sum;
 cin>>n;
 for(int i=1;i<=n;i++)
 {cin.get();
  cin.getline(s,260);
  if(s[0]=='('&&s[strlen(s)-1]==')')
  {if(proba(s)==0) cout<<1<<endl;
   else cout<<0<<endl;
  }
  else cout<<0<<endl;
  return 0;

 }