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:
//package div3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class board
{
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }



    /*
            BABB
            BAABBB

            AAAAABBB

    *  AABBBABBBB
    *
    * AABABB
    *
    * */
    static void helper(String s,int[] a,int n,String match,int inc){
        int i=0;
        while(i<n){
            int j = i;
            if(j+inc-1<=n-1 && s.substring(j,j+inc).equals(match)){
                a[j] = 1;
                i = j+inc-1;
            }
            else{
                i++;
            }
        }

    }
    static final int MAXN = 100000;
    static final int level = 18;



    //static LinkedList<Integer>[] adj;


    static int[] diameter;
    static int bfs(int init, int n)
    {
        // Initializing queue
        Queue<Integer> q = new LinkedList<>();
        q.add(init);

        int visited[] = new int[n + 1];
        for (int i = 0; i <= n; i++)
        {
            visited[i] = 0;
            diameter[i] = 0;
        }

        // Pushing each node in queue
        q.add(init);

        // Mark the traversed node visited
        visited[init] = 1;
        while (q.size() > 0)
        {
            int u = q.peek();
            q.remove();
            for (int nei : adj[u])
            {
                if (visited[nei] == 0)
                {
                    visited[nei] = 1;

                    // Considering weight of edges equal to 1
                    diameter[nei] += diameter[u] + 1;
                    q.add(nei);
                }
            }
        }
        int in = 0;
        for(int i = 0; i <= n; i++)
        {
            if(diameter[i] > diameter[in])
                in = i;
        }

        // return index of max value in diameter
        return in;
    }
    private static int dfs(int node,LinkedList<Integer>[] adj,int parent,int[] sub){

        int size = 1;
        for(int nei : adj[node]){
            if(nei != parent){
                size += dfs(nei,adj,node,sub);
            }
        }
        sub[node] = size;
        return size;
    }
    private static int dfs2(int node,LinkedList<Integer>[] adj,int parent,int[] sub){
        int res = sub[node];
        int maxScore = 0;
        for(int nei : adj[node]){
            if(nei != parent) {
                maxScore = Math.max(maxScore,dfs2(nei,adj,node,sub));
            }
        }
        return res + maxScore;
    }
    public static void primeFactors(long n)
    {
        // Print the number of 2s that divide n
        while (n%2==0)
        {
            primesMap.put((long)2,primesMap.getOrDefault((long)2,0)+1);
            n /= 2;
        }

        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            // While i divides n, print i and divide n
            while (n%i == 0)
            {
                primesMap.put((long)i,primesMap.getOrDefault((long)i,0)+1);
                n /= i;
            }
        }

        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            primesMap.put(n,primesMap.getOrDefault(n,0)+1);
    }
    static TreeMap<Long,Integer> primesMap;
    /*
     *
     *  2 2 2 1 3 4 5
     *  1 2 2 2 3 3 2 1 2 2 2
     * */
    static LinkedList<Integer>[] adj;
    static int[] color;
    static int[] parent;
    static int cycle_end;
    static int cycle_start;
    static int n;
    static HashSet<Integer> cycle;
    static boolean dfs(int v, int par) { // passing vertex and its parent vertex
        color[v] = 1;
        for (int u : adj[v]) {
            if(u == par) continue; // skipping edge to parent vertex
            if (color[u] == 0) {
                parent[u] = v;
                if (dfs(u, parent[u]))
                    return true;
            } else if (color[u] == 1) {
                cycle_end = v;
                cycle_start = u;
                return true;
            }
        }
        color[v] = 2;
        return false;
    }
    static void find_cycle() {
        Arrays.fill(color,0);
        Arrays.fill(parent,-1);
        cycle_start = -1;

        for (int v = 0; v <= n; v++) {
            if (color[v] == 0 && dfs(v, parent[v]))
                break;
        }



        cycle.add(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.add(v);
        cycle.add(cycle_start);
        //System.out.println(cycle);

    }
    static int dfs2(int node,int par){
        int s = 1;
        for(int nei: adj[node]){
            if(!cycle.contains(nei) && nei != par){
                s += dfs2(nei,node);
            }
        }
        return s;
    }
    static long nC2(int n){
        return ((long)(n)*(long)(n-1))/2;
    }
    static int[][] d = new int[][]{{0,0},{1,0},{0,1},{1,1}};
    static Long[][] dp;
    static long go(int start,int i,long[] f,long[] cost,long fuel,int started){
        int s = start,ss = started;
        //System.out.println(fuel);
        if(start != -1 && fuel<0) return Integer.MAX_VALUE;
        if(i >= f.length){
            //System.out.println(start+" "+fuel);
            if(start == -1 ) return Integer.MAX_VALUE;
            if(fuel+1 >= (f.length-(i-1-start))) return 0;
            else return Integer.MAX_VALUE;
        }
        if(start != -1 && dp[i][start] != null) return dp[i][start];
        long totCost = Long.MAX_VALUE;
        if(start == -1) {
            //fuel = 0;
            start = i;
            started = 1;
        }
        fuel += f[i];
        //System.out.println(fuel);
        totCost = Math.min(totCost,cost[i]*f[i] + go(start,i+1,f,cost,fuel-1,started));
        fuel -= f[i];

        totCost = Math.min(totCost,go(s,i+1,f,cost,(s == -1)?0:fuel-1,ss));


        if(s == -1)return totCost;
        return dp[i][s] = totCost;

    }
//    static int go(int index,int x,int k){
//        if(index-k > x || index+)
//        if(index == x) return 0;
//        int op1 = 1+go(index+k,x,k+1);
//        int op2 = 1+go(index-1,x,k+1);
//        return Math.min(op1,op2);
//    }

    public static  int quadraticEquationRoot1(double a, double b, double c){
        double root1, root2; //This is now a double, too.
        root1 = (-b + Math.sqrt(Math.pow(b, 2) - 4*a*c)) / (2*a);
        root2 = (-b - Math.sqrt(Math.pow(b, 2) - 4*a*c)) / (2*a);
        int min = Integer.MAX_VALUE;
        if(root1 >= 0 && root1<min && Math.ceil(root1) == root1)min = (int)root1;
        if(root2 >= 0 && (int)root2<min && Math.ceil(root2) == root2)min = (int)root2;
        if(min == Integer.MAX_VALUE) return -1;
        return min;
    }
    static void print(int[] days){
        for(int i:days)out.print(i+" ");
        out.println();
    }
    static void print(int[][] a){
        for(int[] f:a){
            out.println();
            for(int i:f){
                out.print(i+" ");
            }
        }
        out.println();
    }
    static PrintWriter out;
    static int[] pre;

    static int XOR(int l,int r){
        if(l == 0){
            return pre[r];
        }
        else{
            return pre[r]^pre[l-1];
        }
    }
    static int m = (int)(1e9+7);
    static long prod(long a,long b){
        return (a%m * b%m)%m;
    }
    static List<Long> dfs(int node,LinkedList<Integer>[] adj,int[] a){
        List<Long> ret = new ArrayList<>();
        for(int nei:adj[node]){
            List<Long> get = dfs(nei,adj,a);
            for(long e:get) ret.add(e);
        }
        if(ret.isEmpty()){
            ret.add((long)a[node]);
            return ret;
        }
        Collections.sort(ret);
        long max = ret.get(ret.size()-1);
        int needed = a[node];
        for(int i=0;i<ret.size();i++){
            long diff = max-ret.get(i);
            if(needed > diff){
                ret.set(i,ret.get(i)+diff);
                needed -= diff;
            }
            else{
                ret.set(i,ret.get(i)+needed);
                needed = 0;
                break;
            }
        }
        if(needed > 0){
            for(int i=0;i<ret.size();i++){
                ret.set(i,ret.get(i)+needed/ret.size());
            }
            if(needed%ret.size() != 0){
                ret.set(0,ret.get(0)+needed%ret.size());
            }

        }
        return ret;

    }
    static int manhattan(int[] a,int[] b){
        return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]);
    }
    static boolean satisfy(int[] head,int r,int c,int[][] pre,int[][] suf){
        int diff = r-head[1];
        int want = (1+(diff)*(2))/2 + 1;
        if(pre[r][c] >= want && suf[r][c] >= want) return false;
        return true;
    }
    //int[][] d = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
    static boolean good(char[] s){
        long val = Long.parseLong(String.valueOf(s));
        for(char c:s){
            int dig = c-'0';
            if(dig == 0) continue;
            if(val%dig != 0) return false;
        }
        return true;
    }
    static long gcd(long a, long b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    /*
    *
    *  dp(taken,sum) = dp(taken-1,sum-a[i])+b[i]
    * */
//    double[] a = new double[n];
//    double[] b = new double[n];
//        for(int i=0;i<n;i++){
//    a[i] = sc.nextDouble();
//    b[i] = sc.nextDouble();
//}
//    double[][] dp = new double[n+1][100*n];
//        for(int i=0;i<n;i++){
//
//    for(int taken=i;taken>=0;taken--){
//
//        for(int sum=taken*100;sum>=0;sum--){
//
//            dp[taken][sum] = Math.max(dp[taken][sum],dp[taken-1][sum-(int)a[i]]+b[i]);
//        }
//    }
//}
    static long getClosestFactor(long target, long number) {
        for(long i=target;i>=1;i--){
            if(number%i == 0) return i;
        }
        return -1;
    }

    public static void main(String[] args)
    {
        FastReader sc=new FastReader();
        out = new PrintWriter(System.out);
        int t = sc.nextInt();



        while(t-->0) {
            String s = sc.nextLine();
            if(s.charAt(0) == ')' || s.charAt(s.length()-1) == '(') out.println("NO");
            else{
                if(s.length()%2 == 0) out.println("YES");
                else out.println("NO");
            }


        }





        out.close();
    }


}