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 JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main
{
    /*static class Pair{
        int key;
        int value;
 
        Pair(int key,int value)
        {
            this.key=key;
            this.value=value;
        }
    }
        public static class SortbyKey implements Comparator<Pair>
        {
            public int compare(Pair a, Pair b){
            return (a.key- b.key); 
        }*/
       
    
    public static void process()throws IOException
    {
     String s=nn();
     int op=0,cl=0,n=0;
     for(int i=0;i<s.length();i++)
     {
        char ch=s.charAt(i);
        if(ch=='(')
         op++;
        else if(ch==')')
        cl++;
        else if(ch=='?')
        n++;
     }
     if(s.charAt(0)==')'||s.charAt(s.length()-1)=='('||n%2!=0)
        pn("NO");
    else
        pn("YES");
    }
    
    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new AnotherReader();
        boolean oj = true;
         //PrintWriter out=new PrintWriter("output");
        //oj = System.getProperty("ONLINE_JUDGE") != null;
        //if(!oj) sc=new AnotherReader(100);
 
     // int i=1;
  int T=ni(); while(T-->0)
      //{
       // p("Case #"+i+": ");
            process();
            //i++;
      //}
        long s = System.currentTimeMillis();
      
        out.flush();
        if(!oj)
            System.out.println(System.currentTimeMillis()-s+"ms");
        System.out.close();  
    }
    static void sort(long arr[],int n)
    {
    shuffle(arr,n);
    Arrays.sort(arr);
    }
    static void shuffle(long arr[],int n)
    {
        Random r=new Random();
        for(int i=0;i<n;i++)
        {
          long temp=arr[i];
          int pos=i+r.nextInt(n-i);
          arr[i]=arr[pos];
          arr[pos]=temp;
        }
    }
 
    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);System.out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static String nn()throws IOException{return sc.next();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static long bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    static int[] iarr(int N)throws IOException{int[]ARR=new int[N];for(int i=0;i<N;i++){ARR[i]=ni();}return ARR;}
    static long[] larr(int N)throws IOException{long[]ARR=new long[N];for(int i=0;i<N;i++){ARR[i]=nl();}return ARR;}
    static boolean multipleTC=false;
            
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////
    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
 
    
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
//