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 <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
#include <string>
#include <math.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <array>


#define ll long long int
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define fo(n) for(ll j=0; j<n; j++)
#define fo1(a, n) for(ll j=a; j<n; j++)
#define fov(j,a,n) for(ll j=a; j<n; j++)
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define minv(v) min_element(v.begin(), v.end())
#define maxv(v) max_element(v.begin(), v.end())
#define ubv(v,n) upper_bound(v.begin(), v.end(), n)
#define lbv(v,n) lower_bound(v.begin(), v.end(), n)
#define mll map<ll,ll>
#define mod 1000000007
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define mp make_pair

using namespace std;







/////////////////////////////////////////////////////////////
///////////// FREQUENTLY USED FUNCTIONS (Begin) /////////////
/////////////////////////////////////////////////////////////



///////////// Print an array (vector of long long int) /////////////

void printV(vll& v) {
    for (auto x : v) { cout << x << " "; }
    cout << endl;
}



///////////// Print a matrix (vector of vector of long long int) /////////////

void printVV(vvll& vv) {
    for (auto x : vv) {
        for (auto y : x) { cout << y << " "; }
        cout << endl;
    }
}



///////////// Print a vector of string (each string in new line) /////////////

void printVS(vector<string> v) {
    for (auto x : v) { cout << x << endl; }
}



///////////// Calculate gcd of two numbers /////////////

int gcd(int a, int b) {
    int R;
    while ((a % b) > 0) {
        R = a % b;
        a = b;
        b = R;
    }
    return b;
}



///////////// SubFunction for nCrModPFermat /////////////

ll power(ll x, ll y, ll p)
{
    ll res = 1;

    x = x % p;

    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;

        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}




///////////// Returns n^(-1) mod p /////////////

ll modInverse(ll n, ll p)
{
    return power(n, p - 2, p);
}




///////////// Returns nCrModP using Fermats theorem /////////////

ll nCrModPFermat(ll n, ll r, ll p)
{
    if (r == 0)
        return 1;

    //ll fac[n + 1];
    ll fac[10];
    fac[0] = 1;
    for (ll i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}




///////////// Returns nPrModP using Fermats theorem /////////////

ll nPrModPFermat(ll n, ll r, ll p)
{
    if (r == 0)
        return 1;

    //ll fac[n + 1];
    ll fac[10];
    fac[0] = 1;
    for (ll i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[n - r], p) % p) % p;
}



///////////// SIEVE OF ERATOSTHENES /////////////
// Generate prime numbers less than n
// Takes a ll <n> and vll <ans> as input and fills
// <ans> with the primes upto <n>

void sieve(vll& ans, ll n)
{
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true.
    n = 10000;
    bool prime[10000];
    fo(n) { prime[j] = true; }

    for (ll p = 2; p * p < n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i < n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p < n; p++)
        if (prime[p])
            ans.pb(p);
}

void sieve(vll& ans)
{
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true.
    ll n = 10000;
    bool prime[10000];
    fo(n) { prime[j] = true; }

    for (ll p = 2; p * p < n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i < n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p < n; p++)
        if (prime[p])
            ans.pb(p);
}


///////////////////////////////////////////////////////////
///////////// FREQUENTLY USED FUNCTIONS (End) /////////////
///////////////////////////////////////////////////////////








///////////////////////////////////////////////////
///////////// SOLUTION TO THE PROBLEM /////////////
///////////////////////////////////////////////////


////////////// Function to solve each test case /////////////

int solve() {
    string s; cin >> s;
    ll n = s.size();
    if (n % 2 != 0 || s[0]==')' || s[n-1]=='(') { cout << "NO" << endl; return 0; }
    cout << "YES" << endl; return 0;
}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    cin >> t;
    while (t--) { solve(); }
    return 0;
}