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:
#include<bits/stdc++.h>

using namespace std;

#define iOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
//#define mp make_pair
#define L(x) x.length()
#define B(x) x.begin()
#define E(x) x.end()
#define F(x) x.front()
#define SZ(x) x.size()
#define CLR(x) x.clear()
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define FOR(i,x,y) for(int i=x;i<y;i++)
#define S(x) scanf("%d",&x)
#define SL(x) cin>>x
#define SD(x) scanf("%lf",&x)
#define SC(x) scanf("%1s",&x)
#define SS(x) scanf("%s",x)
#define DUM() scanf("%c",&dum)
#define READ(x) freopen(x,"r",stdin)
#define WRITE(x) freopen(x,"w",stdout)
#define FILL(x,y) memset(x,y,sizeof(x))
#define IT iterator
#define ret(x) return cout<<x,0;
#define rety return cout<<"YES",0;
#define retn return cout<<"NO",0;
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define repn(i,a,b)   for(int i=a;i>=b;i--)
//#define ld long double

using namespace std;
typedef long long int lli;
typedef long double ld;
typedef unsigned long long int llu;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< pii > vpii;
typedef vector< vpii > vvpii;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef map<int,int> mapii;

//const int big=1e7+5;
lli gcd(lli a,lli b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
lli gcdExtended(lli a, lli b, lli *x, lli *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0;
        *y = 1;
        return b;
    }

    lli x1, y1; // To store results of recursive call
    lli gcd = gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of
    // recursive call
    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}
/*
void minDivsieve()
{
    for(long long int i=0;i<=big;++i)
        arr[i]=i;
    for(long long int i=2;i<=big;++i)
    {
        if(arr[i]!=i)
            continue;
        for(long long int j=i;j<=big;j+=i)
            arr[j]=min(arr[j],i);
    }
}*/

/*long long int fac[1000001];

long long int power(long long int x, long long int y,long long int p)
{
    long long int res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
long long int modInverse(long long int n, int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
long long int nCrModPFermat(unsigned long long n,
                                 long long int r, long long int p)
{
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}


*/

//const int inf=1000000007;

/*vector<int> v,r;

int find_set(int x)
{
    if(v[x]==-1)
        return x;
    else
        return find_set(v[x]);
}

void union_set(int x, int y)
{
    x=find_set(x);
    y=find_set(y);
    if(x!=y)
    {
        if(r[x]>r[y])
        {
            r[x]+=r[y];
            v[y]=x;
        }
        else
        {
            r[y]+=r[x];
            v[x]=y;
        }
    }
}*/

//int cnt[400005],pref[400005];


#define all(c) c.begin(),c.end()



long long int mod=1000000007;//998244353;

//lli fact[300005];

/*void factorial()
{
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<300005;++i)
        fact[i]=(fact[i-1]*i);
    //cout<<"here"<<endl;
    return;
}
*/
long long int binpower(long long int a, long long int b)
{
    long long int ans=1;
    while(b>0)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

bool isPrime(int n)
{
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
/*lli gprime[1000001];
void grsieve()
{
    memset(gprime,0,sizeof(gprime));
    gprime[1]=1;
    gprime[0]=0;
    for(lli i=2;i<1000001;++i)
    {
        if(gprime[i]==0)
        {
            for(lli j=i;j<1000001;j+=i)
                gprime[j]=i;
        }
    }
}*/


/*const int maxn=300001;
bool checkprimes[maxn];
//lli fact[maxn];
vector<lli>primes;
void primechecker()
{
    for(lli i=2;i<maxn;++i)
    {
        if(checkprimes[i]==false)
        {
            primes.pb(i);
            for(lli j=i;j<maxn;j+=i)
            {
                checkprimes[j]=true;
            }
        }
    }
}

void factcalc()
{
    fact[0]=1; fact[1]=1;
    for(lli i=2;i<maxn;++i)
    {
        fact[i]=(fact[i-1]*i)%mod;
    }
}

lli C(lli a, lli b)
{
    //cout<<mod<<endl;
    //cout<<a<<" fact[a]: "<<fact[a]<<endl;
    lli c=(fact[a]*fact[b-a])%mod;
    //cout<<c<<endl;
    //cout<<binpower(c,mod-2)<<endl;
    lli res=(fact[b]*binpower(c,mod-2))%mod;
    return res;
}*/



/*
lli C(int u,int v)   //uCv
{
    lli c=(fact[v]*fact[u-v])%mod;
    lli in=binpower(c,mod-2);
    lli res=(in*fact[u])%mod;
    return res;
}
*/

/*int sz[200005],p[200005];
int get(int a)
{
    if(a==p[a])
        return a;
    return p[a]=get(p[a]);
}
void add(int a, int b)
{
    a=get(a);
    b=get(b);
    if(a==b)
        return;

    if(sz[a]>sz[b])
    {
        p[b]=a;
        sz[a]+=sz[b];
    }
    else
    {
        p[a]=b;
        sz[b]+=sz[a];
    }
    return;
}*/

/*const int N=1000005;
bool primes[N];
int cummp[N];
void sieve()
{
    for(int i=0;i<N;++i)
        primes[i]=true;
    primes[0]=false; primes[1]=false;
    for(int i=2;i<N;++i)
    {
        if(primes[i])
        {
            for(int j=2*i;j<N;j+=i)
                primes[j]=false;
        }
    }
}

void cum()
{
    memset(cummp,0,sizeof(cummp));
    for(int i=1;i<N;++i)
    {
        cummp[i]=cummp[i-1];
        if(primes[i])
            cummp[i]++;
    }
}

int sq[N];
void sqcalc()
{
    for(int i=0;i<N;++i)
        sq[i]=-1;
    for(int i=1;i*i<=N;++i)
    {
        sq[i*i]=i;
    }
    for(int i=1;i<N;++i)
    {
        if(sq[i]==-1)
            sq[i]=sq[i-1];
    }
}*/

int bits(lli a)
{
    return __builtin_popcount(a);
}

/*struct item{
    int m,c;
};

struct segtree{
    int sz;
    vector<lli>sums;

    void init(int n)
    {
        sz=1;
        while(sz<n)
            sz*=2;
        sums.assign(2*sz+1,0ll);
    }

    void sett(int i, int v, int x, int lx, int rx)
    {
        if(rx-lx==1)
        {
            sums[x]=v;
            return;
        }
        int m=(lx+rx)/2;
        if(i<m)
            sett(i,v,2*x+1,lx,m);
        else
            sett(i,v,2*x+2,m,rx);
        sums[x]=sums[2*x+1]+sums[2*x+2];
    }
    void sett(int i, int v)
    {
        sett(i,v,0,0,sz);
    }

    lli sum(int l, int r, int x, int lx, int rx)
    {
        if(l>=rx || lx>=r)
            return 0;
        if(l<=lx && rx<=r)
            return sums[x];
        int m=(lx+rx)/2;
        lli s1=sum(l,r,2*x+1,lx,m);
        lli s2=sum(l,r,2*x+2,m,rx);
        return s1+s2;
    }

    lli sum(int l, int r)
    {
        return sum(l,r,0,0,sz);
    }

};*/

int main()
{
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    iOS;
    lli test=1;
    /*sieve(); cum();
    sqcalc();*/
    cin>>test;
    while(test--)
    {
        string s;
        cin>>s;
        int q=s.length()-2;
        if(q%2==1)
            cout<<"NO";
        else if(s[0]==')')
            cout<<"NO";
        else if(s[s.length()-1]=='(')
            cout<<"NO";
        else
            cout<<"YES";
        cout<<endl;
    }
    /* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

    return 0;
}