Problem: A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters + and 1 into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not. Let's call a regular bracket sequence "RBS".

You are given a sequence s of n characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.

You have to replace every character ? with either ) or ( (different characters ? can be replaced with different brackets). You cannot reorder the characters, remove them, insert other characters, and each ? must be replaced.

Determine if it is possible to obtain an RBS after these replacements.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

Each test case consists of one line containing s (2 ≤ |s| ≤ 100) — a sequence of characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.

Output

For each test case, print YES if it is possible to obtain a regular bracket sequence, or NO otherwise}. 

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

Example

Input


5
()
(?)
(??)
??()
)?(?


Output


YES
NO
YES
YES
NO

Note

In the first test case, the sequence is already an RBS.

In the third test case, you can obtain an RBS as follows: ()() or (()).

In the fourth test case, you can obtain an RBS as follows: ()().

Solution (in CPP):

Solution:
// my code goes here 
// HITESH VISHNOI  MANIT SE HU 
//                                <only constrains are imaginary but, I AM REAL.........>
#include<bits/stdc++.h>
using namespace std;
#define   int             long long
#define   f(a,b,n)        for(ll a=b;a<n;a++)
#define   readarr(arr,n)  f(i,0,n) cin>>arr[i];
#define   ll              long long 
#define   pb              push_back
#define   go              ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define   ms(a,i)         memset(a,i,sizeof(a))
#define   mod             1000000007  //1e9+7 ans%mod
#define   w(t)            int t; cin>>t; while(t--)
#define   MOD              1e9+7
#define   setbits(x)      __builtin_popcountll(x)
#define   zrobits(x)      __builtin_ctzll(x)
#define   vi              vector<int>
#define   mp              map<int,int>
#define   pi              pair<int,int>
#define   inf             1e18
#define   ff              first
#define   ss              second
#define   ps(x,y)         fixed <<setprecision(y)<<x
#define   yes             cout <<"YES" << endl 
#define   no              cout <<"NO" << endl 

void pseudo()
{   go;
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
}
long long hcf(long long a,long long b){
	long long greater=a>b?a:b;
	long long lesser=a<b?a:b;
	return hcf(greater,lesser);	
}

long long lcm(long long a,long long b){
	return a*b/hcf(a,b);
}

int32_t main ()
{
	pseudo() ;
	w(t)
	{
		string s ;
		 cin >> s ;
		int q =0; 
		int open=0,close=0 ;

		bool flag = false ;
		int n= s.size() ;

		if (s[0]==')' or s[n-1] =='(') 
			flag=1 ;
		else
		{
			f(i,0,n)
		{
				if(s[i]=='?') q++;
				if(s[i]=='(') open++;
				if(s[i]==')') close++;
		}

			int d = abs(open- close) ;

			if (d==0 and q%2!=0)
				flag=1 ;
			else 	if (d!=0 and d!=q)
				{
					flag = 1;
				}
		}
			if(flag)	no ;	else  yes ;	
	}
	return 0 ;
}