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;
template <typename T1, typename T2, typename T3>
struct triplet {T1 first; T2 second; T3 third;
    triplet() {first = T1(); second = T2(); third = T3();}
    triplet(T1 a, T2 b, T3 c) {first = a, second = b, third = c;}
};
using ll = long long;
using ld = long double;
using pi = pair <int, int>;
using ti = triplet <int, int, int>;
using pl = pair <ll, ll>;
using tl = triplet <ll, ll, ll>;
#define pb push_back
#define fi first
#define se second
#define th third
#define ALL(a) (a).begin(),(a).end()
#define ALLR(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define FOR(i,j,k) for(int i=(j);i<=(k);++i)
#define RFOR(i,j,k) for(int i=(j);i>=(k);--i)

const int INF    = ~(1 << 31);
const int MININF =  (1 << 31);
const ll LNF     = ~(1LL << 63);
const ll MINLNF  =  (1LL << 63);
const ll MOD1    = 1e9 + 7;
const ll MOD9    = 998244353;

ll quick_pow(ll x,ll y,int Mod){
    ll res=1;
    while(y){
        if(y&1)res=res*x%Mod;
        x=x*x%Mod,y>>=1;
    }
    return res;
}
ll inv(ll x,int Mod){return quick_pow(x,Mod-2,Mod);}
ll moddiv(ll a, ll b, int Mod){return 1LL * a * inv(b, Mod) % Mod;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}

int n, m, x, y;
string s;

void Input() {
    cin >> s;
}

void Solve() {
    pi x = {0, 0};
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == '(') x.fi = i;
        if(s[i] == ')') x.se = i;
    }
    int n = (int)s.length();
    bool ok = (n % 2 == 0) && x.fi != n - 1 && x.se != 0;
    ans2(ok);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while(t--) {
        Input();
        Solve();
    }
    return 0;
}