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

Solution:
from __future__ import division, print_function


def main():
    # Template 1.0
    import sys, re, math
    from collections import deque, defaultdict, Counter, OrderedDict
    from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, floor, log
    from heapq import heappush, heappop, heapify, nlargest, nsmallest
    def STR():
        return list(input())

    def INT():
        return int(input())

    def MAP():
        return map(int, input().split())

    def LIST():
        return list(map(int, input().split()))

    def list2d(a, b, c):
        return [[c] * b for i in range(a)]

    def computeGCD(x, y):

        while (y):
            x, y = y, x % y

        return x

    def sortListWithIndex(listOfTuples, idx):
        return (sorted(listOfTuples, key=lambda x: x[idx]))

    def sortDictWithVal(passedDic):
        temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
        toret = {}
        for tup in temp:
            toret[tup[0]] = tup[1]
        return toret

    def sortDictWithKey(passedDic):
        return dict(OrderedDict(sorted(passedDic.items())))

    INF = float('inf')
    mod = 10 ** 9 + 7



    t = INT()

    while (t != 0):
        ans = "NO"
        s = input()
        f = 0
        for ch in s:
            if(ch=='('):
                f = 1
                break
            elif(ch==')'):
                break
        if(f==1):
            a,b,c = 0, 0, 0
            i = 0
            for i in range(len(s)):
                ch = s[i]
                if(ch!='('):
                    a+=1
                else:
                    break

            for j in range(i+1, len(s)):
                ch = s[j]
                if(ch!=')'):
                    b+=1
                else:
                    break
            for k in range(j+1, len(s)):
                c+=1
            if(a%2==0):
                if((b%2==0 and c%2==0) or (b%2==1 and c%2==1)):
                    ans = "YES"
            else:
                if ((b % 2 == 0 and c % 2 == 1) or (b % 2 == 1 and c % 2 == 0)):
                    ans = "YES"
        else:
            a, b, c = 0, 0, 0
            i = 0
            for i in range(len(s)):
                ch = s[i]
                if (ch != ')'):
                    a += 1
                else:
                    break

            for j in range(i + 1, len(s)):
                ch = s[j]
                if (ch != '('):
                    b += 1
                else:
                    break
            for k in range(j + 1, len(s)):
                c += 1
            if(a!=0 and c!=0):
                if (a % 2 == 0):
                    if ((b % 2 == 0 and c % 2 == 0) or (b % 2 == 1 and c % 2 == 1)):
                        ans = "YES"
                else:
                    if ((b % 2 == 0 and c % 2 == 1) or (b % 2 == 1 and c % 2 == 0)):
                        ans = "YES"
        print(ans)
        t -= 1


'''
8
)?(??
??)??(??
?)????(???
?)?(?
??)??(?
?)?(??
?)??(????
??)?(?

'''
######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip

    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192


class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda: self.buffer.read().decode('ascii')
            self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys


class ostream:
    def __lshift__(self, a):
        sys.stdout.write(str(a))
        return self


cout = ostream()
endl = '\n'


# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero=0):
    conv = ord if py2 else lambda x: x
    A = [];
    numb = zero;
    sign = 1;
    i = 0;
    s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0'[0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-'[0]:
                sign = -1
            elif s[i] != b'\r'[0]:
                A.append(sign * numb)
                numb = zero;
                sign = 1
            i += 1
    except:
        pass
    if s and s[-1] >= b'0'[0]:
        A.append(sign * numb)
    return A


if __name__ == "__main__":
    main()