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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;


public class Edu101 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>primes;
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>h;
	static boolean[]v;
	static int[]a,b,c;
	static long[]l,dp;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		A();
		//sieveOfEratosthenes(1000000);
		//B();
		//C();
		//minimum for subarrays of fixed length
		//D();
		out.close();
	}
	  private static void A() throws IOException {
		 int t=sc.nextInt();
		 while(t-->0) {
			String s=sc.next();
			int idx1=-1,idx2=-1;
		
			for(int i=0;i<s.length();i++) {
				if(s.charAt(i)=='(') {
					idx1=i;
				}
				if(s.charAt(i)==')') {
					idx2=i;
				}
			}
			out.println(s.length()%2==0&&idx1!=s.length()-1&&idx2!=0?"YES":"NO");
//			if(idx1>idx2) {
//				int pt1=idx2,pt2=idx1-idx2-1,pt3=s.length()-1-idx1;
//				if(pt1!=0&&pt3!=0&&pt2%2==0&&(pt1==pt3||pt1%2==1&&pt3%2==1)) {
//					out.println("YES");
//				}else {
//					out.println("NO");
//				}
//			}else {
//				int pt1=idx1,pt2=idx2-idx1-1,pt3=s.length()-1-idx2;
//				if((pt1==pt3||pt1%2==0&&pt3%2==0)&&pt2%2==0) {
//					out.println("YES");
//				}else {
//					out.println("NO");
//				}
//			}
		 }
		
	}
	  static void C() throws IOException {
			int t=sc.nextInt();
			while(t-->0) {
				int n=sc.nextInt(),k=sc.nextInt();
				a=sc.nextArrInt(n);
				int max=0;
				boolean f=true;
				for(int i=0;i<a.length-1;i++) {
					if(a[i]>=k) {
						f=false;
						break;
					}
					 if(a[i]==k-1&&a[i+1]==k-1) {
			    		 f=false;
			    		 break;
			    	 }
					max=Math.max(max, a[i]);
				}
				if(a[n-1]>=k)f=false;
				out.println(f?"YES":"NO");
				
				
			}		
		}
	static void B() throws IOException {
		int t=sc.nextInt();
		while(t-->0) {
			int n=sc.nextInt();
			a=sc.nextArrInt(n);
			int m=sc.nextInt();
			b=sc.nextArrInt(m);
			int mx1=0,mx2=0,s1=0,s2=0;
			for(int i=0;i<a.length;i++) {
				s1+=a[i];
				mx1=Math.max(mx1, s1);
			}
			for(int i=0;i<b.length;i++) {
				s2+=b[i];
				mx2=Math.max(mx2, s2);
			}
			out.println(mx1+mx2);
			
		}
	}

	
	static void D() throws IOException {
		int t=sc.nextInt();
		while(t-->0) {
			int n=sc.nextInt();
		
	}
}
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

	}
}