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>

#define PRECISION(x) cout << fixed << setprecision(x);
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

#define pb push_back
#define pii array<int,2>
#define pll array<long long,2>
#define tii array<int,3>
#define tll array<long long,3>

#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define watch(x) cout << (#x) << " is " << (x) << endl

typedef long long ll;

const double PI=acos(-1);
const int MOD = 1000000007;
const double eps = 1e-9;

template<typename T1, typename T2>
ostream& operator<< (ostream& out, const pair<T1, T2>& v) {
    out << "{" << v.first << ","<< v.second << "}";
    return out;
}

template<typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
    out << "[";
    size_t last = v.size() - 1;
    for (size_t i = 0; i < v.size(); ++i) {
        out << v[i];
        if (i != last)
            out << " ";
    }
    out << "]\n";
    return out;
}

template<typename T> T gcd(T a, T b)
{
    return(b?__gcd(a,b):a);
}

int mul(int a, int b, int c = MOD)
{
    ll res=(ll)a*b;
    return(res>=c?res%c:res);
}

template<typename T>T power(T e, T n, T m = MOD)
{
    T x=1,p=e;
    while(n)
    {
        if(n&1)
            x=mul(x,p,m);
        p=mul(p,p,m);
        n>>=1;
    }
    return x;
}

template<typename T>
using vec = vector<T>;

template<typename T>
using vvec = vector< vector<T> >;

template<typename T>
using vvvec = vector< vector< vector<T> > >;

int main()
{
    FAST_IO;
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        stack<char> st;
        int n = s.length();

        if(n%2==1)
        {
            cout<<"No\n";
            continue;
        }
        int count = 0;
        REP(i,n)
        {
            if(s[i]=='?')
            {
                if(count<n/2 - 1)
                {
                    s[i] = '(';
                    count++;
                }
                else
                {
                    s[i] = ')';
                    count++;
                }
            }
        }

        bool flag = true;
        for(int i = 0; i < n; i++)
        {
            if(s[i]=='(')
            {
                st.push('(');
            }
            else
            {
                if(st.empty())
                {
                    flag = false;
                    break;
                }
                else
                {
                    st.pop();
                }
            }
        }

        if(flag)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}