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<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<stack>
using namespace std;

int partitions(int arr[] , int s , int e)
{
    int i=s;
    int pivot = arr[e];
    for(int j=s ; j<=e-1 ; j++)
    {
        if(pivot>arr[j])
        {
            swap(arr[i],arr[j]);
            i++;
        }
    }
    swap(arr[i],arr[e]);
    return i;
}

void quickSort(int arr[] , int s , int e)
{
    if(s>=e)
    {
        return;
    }
    int p = partitions(arr , s , e);
    quickSort(arr , s , p-1);
    quickSort(arr , p+1 , e);
}

bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}

int binary(int arr[] , int n , int  key)
{
    int l,h,mid;
    l=0;
    h=n;
    while(l<=h)
    {
        mid=(l+h)/2;
        if(key==arr[mid])
        {
            return mid;
        }
        else if(key<arr[mid])
        {
            h=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    return -1;
}

int repeat(int arr[] , int n)
{
    if(arr[0]!=arr[1])
        {
            return arr[0];
        }
    for(int i=1 ; i<n-1 ; i++)
    {
        if(arr[i]!=arr[i+1] && arr[i]!=arr[i-1])
        {
            return arr[i];
        }
    }
    if(arr[n-1]!=arr[n-2])
    {
        return arr[n-1];
    }
    return -1;
}
int arraySortedOrNot(int arr[], int n)
{
    // Array has one or no element or the
    // rest are already checked and approved.
    if (n == 1 || n == 0)
        return 1;

    // Unsorted pair found (Equal values allowed)
    if (arr[n - 1] < arr[n - 2])
        return 0;

    // Last pair was sorted
    // Keep on checking
    return arraySortedOrNot(arr, n - 1);
}

int factorial(int n)
{
    // single line to find factorial
    return (n==1 || n==0) ? 1: n * factorial(n - 1);
}

struct permute{

    int red;
    int blue;

};

void permut(string str1 , string str2)
{
    int countr=0;
    int countb = 0;
    sort(str1.begin() , str1.end());
    sort(str2.begin() , str2.end());
    do{
        int a = stoi(str1);
        int b = stoi(str2);
        if(a>b)
        {
            countr++;
        }
        else if(a<b)
        {
            countb++;
        }
        else if(a==b)
        {
            countr++;
            countb++;
        }
    }while(next_permutation(str1.begin() , str1.end()) && next_permutation(str2.begin() , str2.end()));
    if(countr > countb)
    {
        cout<<"RED"<<endl;
    }
    else if(countr<countb)
    {
        cout<<"BLUE"<<endl;
    }
    else
    {
        cout<<"EQUAL"<<endl;
    }
}

int main()
{
    int t;
    cin>>t;
    struct permute per;
    for(int i=0 ; i<t  ; i++)
    {
        string str;
        cin>>str;
        int n = str.length();
        int count=0;
        if(str[0] == ')' || str[n-1] == '(')
        {
            cout<<"NO"<<endl;
        }
        else
        {
            for(int j=0 ; j<n ; j++)
            {
                if(str[j]=='?')
                {
                    count++;
                }
            }
            if(count%2==0)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
    }

    return 0;
}