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 \le t \le 1000$) — the number of test cases.

Each test case consists of one line containing $s$ ($2 \le |s| \le 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).


-----Examples-----

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: ()().

Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for i in range(0, int(input())):
	s = input()
	if len(s) % 2 != 0:
		print('NO')
	elif s[0] == ')' or s[-1] == '(':
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	if len(s) % 2 == 1 or s[0] == ')' or s[-1] == '(':
		print('NO')
		continue
	print('YES')


for _ in range(int(input())):
	a = input()
	if len(a) % 2 != 0 or a[0] == ')' or a[-1] == '(':
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	f = False
	ans = False
	for i in s:
		if i == '(':
			f = True
		if i == ')' and f:
			ans = True
	if ans and s.count('?') % 2 == 0 or (s[0] != ')' and s[-1] != '(' and (s.count('?') % 2 == 0)):
		print('YES')
	else:
		print('NO')


def check(s):
	if len(s) % 2 != 0:
		return False
	if s[0] == ')' or s[-1] == '(':
		return False
	return (len(s) - 2) % 2 == 0
t = int(input())
for _ in range(t):
	s = input()
	if check(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	l = r = q = 0
	for c in s:
		if c == '(':
			l += 1
		if c == ')':
			r += 1
		if c == '?':
			q += 1
	if (l + r + q) % 2:
		print('NO')
		continue
	lq = (l + r + q) // 2 - l
	if not 0 <= lq <= q:
		print('NO')
		continue
	works = True
	d = 0
	for c in s:
		if c == '(':
			d += 1
		if c == ')':
			d -= 1
		if c == '?':
			if lq:
				lq -= 1
				d += 1
			else:
				d -= 1
		if d < 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	if len(s) % 2 == 0:
		if s[0] == '(':
			print('Yes')
		elif s[0] == ')':
			print('No')
		elif s[len(s) - 1] == '(':
			print('No')
		else:
			print('Yes')
	else:
		print('No')


try:
	test = int(input())
	while test != 0:
		string = input()
		left = string.index('(')
		right = string.index(')')
		if left < right:
			before = left - 0
			mid = right - left - 1
			after = len(string) - 1 - right
			if mid + before + after & 1 == 0:
				print('Yes')
			else:
				print('No')
		else:
			before = right - 0
			mid = left - right - 1
			after = len(string) - 1 - left
			if before - 1 >= 0 and after - 1 >= 0 and (mid + (before - 1) + (after - 1) & 1 == 0):
				print('Yes')
			else:
				print('No')
		test -= 1
except EOFError as e:
	print('')


t = int(input())
for i in range(t):
	s = input()
	if len(s) % 2 == 0 and s[0] != ')' and (s[-1] != '('):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	f = 1
	o = 0
	q = 0
	c = 0
	for i in range(len(s)):
		if s[i] == '(':
			o = o + 1
		elif s[i] == ')':
			c = c + 1
			if o > 0:
				o = o - 1
			elif q > 0:
				q = q - 1
			else:
				f = 0
				break
		else:
			q = q + 1
	if len(s) % 2 != 0 or s[0] == ')' or s[len(s) - 1] == '(':
		print('NO')
	elif f == 0:
		print('NO')
	elif (o + q) % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input().strip('\n')
	cnt = 0
	cnt1 = 0
	cnt2 = 0
	f = 0
	if s[0] == ')' or s[-1] == '(':
		f = 1
	else:
		for i in s:
			if i == ')':
				cnt2 += 1
			if i == '?':
				cnt += 1
			if i == '(':
				cnt1 += 1
		d = abs(cnt1 - cnt2)
		if d == 0 and cnt % 2 != 0:
			f = 1
		elif d != 0 and d != cnt:
			f = 1
	if f:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	n = len(s)
	op = s.index('(')
	cl = s.index(')')
	if s[0] == ')' or s[-1] == '(' or n & 1:
		print('NO')
	else:
		print('YES')


import math
from sys import *

def solve():
	s = input()
	n = len(s)
	if s[n - 1] == '(' or s[0] == ')':
		print('NO')
	else:
		(c1, c2, c3) = (0, 0, 0)
		for i in s:
			if i == '(':
				c1 += 1
			elif i == ')':
				c2 += 1
			elif i == '?':
				c3 += 1
		if abs(c1 - c2) == 0 and c3 % 2 != 0:
			print('NO')
		elif abs(c1 - c2) != 0 and abs(c1 - c2) != c3:
			print('NO')
		else:
			print('YES')
t = int(input())
while t > 0:
	t -= 1
	solve()


for _ in ' ' * int(input()):
	i = input()
	i = list(str(i))
	l = i.count('(')
	r = i.count(')')
	q = i.count('?')
	if i[0] == ')' or i[-1] == '(':
		print('NO')
	elif (l + r + q) % 2 == 0:
		print('YES')
	else:
		print('NO')


import os
import sys
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def main():
	try:
		for _ in range(inp()):
			s = input()
			c = 0
			f = False
			for i in s:
				if i == '(':
					f = True
					c += 1
				elif i == ')':
					if f:
						if c > 0:
							c -= 1
						else:
							c += 1
					else:
						c -= 1
				else:
					f = True
					if c > 0:
						c -= 1
					else:
						c += 1
				if c < 0:
					print('NO')
					break
			else:
				if c == 0:
					print('YES')
				else:
					print('NO')
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		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')
main()


t = int(input())
while t:
	t -= 1
	s = input()
	if s[0] != ')' and s[-1] != '(' and (len(s) % 2 == 0):
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()[:-1]
	x = len(s)
	a = s.count('(')
	b = s.count(')')
	c = x - a - b
	if x % 2 == 0:
		if max(a, b) - min(a, b) <= c:
			if s[0] == ')' or s[-1] == '(':
				print('NO')
			else:
				print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for i in range(t):
	a = input()
	if len(a) % 2 != 0:
		print('NO')
	elif a[0] == ')' or a[len(a) - 1] == '(' or a.count('(') > len(a) // 2 or (a.count(')') > len(a) // 2):
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	o = s.index('(')
	c = s.index(')')
	count = s.count('?')
	if o < c:
		if count % 2 == 0:
			res = 'YES'
		else:
			res = 'NO'
	elif s[:c].count('?') > 0 and s[o:].count('?') > 0 and (s.count('?') % 2 == 0):
		res = 'YES'
	else:
		res = 'NO'
	print(res)


def func(string):
	ref = ''
	for i in range(len(string)):
		if string[i] == '(' or string[i] == ')':
			ref += string[i]
	if ref == '()' and len(string) % 2 == 0:
		return True
	if len(string) % 2 != 0:
		return False
	if string[-1] == '(' or string[0] == ')':
		return False
	return True
t = int(input())
while t > 0:
	s = str(input().strip())
	if func(s):
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	s = input().strip()
	if len(s) % 2 != 0 or s[0] == ')' or s[-1] == '(':
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	cntl = 0
	cntr = 0
	cntq = 0
	for i in range(n):
		if s[i] == '(':
			cntl += 1
		elif s[i] == ')':
			cntr += 1
		else:
			cntq += 1
	max_ = max(cntl, cntr)
	nokoril = max_ - cntl
	nokorir = max_ - cntr
	cntq -= nokoril + nokorir
	if cntq % 2 == 1:
		print('NO')
		continue
	nokoril += cntq // 2
	nokorir += cntq // 2
	val = 0
	min_val = 0
	for i in range(n):
		if s[i] == '(':
			val += 1
		elif s[i] == ')':
			val -= 1
			min_val = min(val, min_val)
		elif nokoril > 0:
			val += 1
			nokoril -= 1
		else:
			val -= 1
			min_val = min(val, min_val)
	if min_val < 0:
		print('NO')
	else:
		print('YES')


t = int(input())
a = []
for i in range(t):
	s = input()
	a.append(s)
for i in range(t):
	if len(a[i]) % 2 != 0 or a[i][0] == ')' or a[i][-1] == '(' or (abs(a[i].count('(') - a[i].count(')')) > a[i].count('?')):
		print('NO')
	else:
		print('YES')


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = ri()
	for _ in range(tc):
		s = rs()
		if s.count('?') % 2 or s[0] == ')' or s[-1] == '(':
			print('NO')
		else:
			print('YES')
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

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

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import math
from collections import defaultdict as dfc
from collections import Counter
from math import gcd

def SOE(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	l = []
	for p in range(2, n + 1):
		if prime[p]:
			l += [p]
	return l

def i1():
	return int(input())

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

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

def i4():
	return input()
for i in range(i1()):
	s = i4()
	n = len(s)
	c1 = 0
	c = 0
	if n % 2 != 0:
		print('NO')
	else:
		for i in s:
			if i == '(' or i == '?':
				c1 = c1 + 1
			elif c1 > 0:
				c1 = c1 - 1
			else:
				c = 1
				break
		if c > 0:
			print('NO')
		else:
			c2 = 0
			for i in s:
				if i == '(':
					c2 += 1
				else:
					c2 -= 1
					c2 = max(c2, 0)
			if c2 > 0:
				print('NO')
			else:
				print('YES')


for _ in range(int(input())):
	lis = list(map(str, list(input())))
	x = len(lis)
	if x % 2 == 1 or lis[0] == ')' or lis[-1] == '(':
		print('NO')
	else:
		print('YES')


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
fast_reader = sys.stdin.readline
fast_writer = sys.stdout.write

def input():
	return fast_reader().strip()

def print(*argv):
	fast_writer(' '.join((str(i) for i in argv)))
	fast_writer('\n')
for _ in range(int(input())):
	s = input()
	n = len(s)
	if n % 2 != 0:
		print('NO')
	elif s.index('(') < s.index(')'):
		print('YES')
	elif s[0] == '?' and s[-1] == '?':
		print('YES')
	else:
		print('NO')


t = int(input())
for t in range(0, t):
	str = input()
	if len(str) % 2 == 0 and str[0] != ')' and (str[-1] != '('):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	if s[0] == ')' or s[-1] == '(' or s.count('?') % 2 != 0:
		print('NO')
	else:
		print('YES')


def is_RSB(s):
	if len(s) % 2 == 1:
		return 'NO'
	n = len(s)
	if s[0] == ')':
		return 'NO'
	if s[n - 1] == '(':
		return 'NO'
	return 'YES'
no_tests = int(input())
res = []
for i in range(no_tests):
	s = input()
	res.append(is_RSB(s))
for each in res:
	print(each)


for w in range(int(input())):
	s = str(input())
	n = len(s)
	if n % 2 != 0:
		print('NO')
	else:
		i1 = s.find('(')
		i2 = s.find(')')
		if i2 == 0 or i1 == n - 1:
			print('NO')
		else:
			print('YES')


import sys
input = sys.stdin.readline
from sys import stdin, stdout
from collections import defaultdict, Counter
M = 10 ** 9 + 7

def main():
	for _ in range(int(input())):
		s = input().strip()
		n = len(s)
		i = s.find('(')
		j = s.find(')')
		if n % 2:
			print('NO')
		elif i > j:
			if i == n - 1 or j == 0:
				print('NO')
			else:
				print('YES')
		else:
			print('YES')
main()


T = int(input())
for _ in range(T):
	s = input()
	if len(s) % 2 == 0 and s[0] != ')' and (s[-1] != '('):
		print('YES')
	else:
		print('NO')


import os
import sys
from io import BytesIO, IOBase
_print = print
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		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')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def solve():
	s = inp()
	if len(s) & 1:
		return ''
	mn = mx = 0
	for c in s:
		if c == '(':
			mn += 1
			mx += 1
		elif c == ')':
			mn = max(mn - 1, 0)
			mx -= 1
		else:
			mn = max(mn - 1, 0)
			mx += 1
		if mx < 0:
			return False
	if not mn <= 0:
		return False
	return True

def main():
	for _ in range(itg()):
		print('YES' if solve() else 'NO')
DEBUG = 0
URL = ''
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
else:
	if DEBUG != 2:
		(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	if DEBUG:

		def print(*args, **kwargs):
			_print(*args, **kwargs)
			sys.stdout.flush()
	main()


for _ in range(int(input())):
	s = input()
	ok = True
	if len(s) & 1:
		ok = False
	if s[0] == ')' or s[len(s) - 1] == '(':
		ok = False
	if ok:
		print('YES')
	else:
		print('NO')


def solve(s):
	if s[0] == ')' or s[-1] == '(' or len(s) % 2 == 1:
		print('NO')
	else:
		print('YES')
tcs = int(input())
for i in range(tcs):
	s = input()
	solve(s)


n = int(input())
for i in range(n):
	s = input()
	Ans = 'YES'
	sum = 0
	life = 0
	f = 0
	for x in s:
		if x == '(':
			sum += 1
		elif x == ')':
			sum -= 1
		elif x == '?':
			life += 1
		if sum < 0:
			if life > 0:
				sum = 0
				life -= 1
				f = 1
			else:
				Ans = 'NO'
				break
		if f == 1 and sum > 0:
			if x == s[-1]:
				Ans = 'NO'
				break
			else:
				sum = 0
				life -= 1
	if life % 2 == 1:
		Ans = 'NO'
	print(Ans)


len_br = int(input())
for i in range(0, len_br):
	b_mark = 0
	q_mark = 0
	bracket = list(input())
	if bracket[0] == ')' or bracket[-1] == '(':
		print('No')
	else:
		for j in range(0, len(bracket)):
			if bracket[j] == '?':
				q_mark += 1
			elif bracket[j] == '(' or ')':
				b_mark += 1
		if q_mark % 2 == 0 and b_mark % 2 == 0:
			print('Yes')
		else:
			print('No')


t = int(input())
for x in range(t):
	a = input()
	if '(' not in a and ')' not in a:
		if len(a) % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif '?' not in a:
		if a == '()':
			print('YES')
		else:
			print('NO')
	elif a.index('(') < a.index(')'):
		if a.count('?') % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		ar = a.index('(')
		al = a.index(')')
		if a.count('?') % 2 == 0 and al != 0 and (ar != len(a) - 1):
			print('YES')
		else:
			print('NO')


def func():
	n = int(input())
	for _ in range(n):
		s = input().strip()
		if len(s) % 2 == 0 and (not s.startswith(')')) and (not s.endswith('(')):
			print('YES')
		else:
			print('NO')
func()


t = int(input())
while t:
	a = input()
	n = len(a)
	if a[0] == ')' or a[n - 1] == '(':
		print('NO')
	elif a.count('?') % 2 == 1:
		print('NO')
	else:
		print('YES')
	t -= 1


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	s = input().strip()
	if len(s) % 2 > 0:
		print('NO')
		continue
	if s[0] == ')' or s[-1] == '(':
		print('NO')
		continue
	print('YES')


import sys, os, io
input = sys.stdin.readline
for _ in range(int(input())):
	s = input().strip()
	cnt = 0
	temp = 0
	temp1 = 0
	flag = 0
	for i in s:
		if i == '(':
			cnt += 1
		elif i == ')':
			cnt -= 1
		else:
			temp += 1
			temp1 += 1
			temp1 = min(temp1, cnt)
		if cnt < 0:
			if temp == 0:
				flag = 1
				break
			cnt = 0
			temp -= 1
	if cnt > temp1:
		flag = 1
	temp -= cnt
	if temp % 2:
		flag = 1
	if flag:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	seq = list(input())
	if len(seq) % 2 != 0:
		print('NO')
	elif seq[0] == ')' or seq[-1] == '(':
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	x = input()
	if x[0] != ')' and x[-1] != '(' and (len(x) % 2 == 0):
		print('YES')
	else:
		print('NO')


from sys import stdin
inp = stdin.read()
lst = list(inp.split())
seq = lst[1:len(lst)]
for i in seq:
	if i.count('?') % 2 != 0 or i[0] == ')' or i[len(i) - 1] == '(':
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	if len(s) % 2 != 0:
		print('NO')
	elif s.startswith(')'):
		print('NO')
	elif s.endswith('('):
		print('NO')
	else:
		lb = [s.count('('), s.count(')')]
		qb = s.count('?')
		if lb[1] > lb[0] + qb:
			print('NO')
		elif (lb[1] - lb[0] + qb) % 2 != 0:
			print('NO')
		else:
			print('YES')


f = len
for _ in range(int(input())):
	s = input()
	n = f(s)
	if n & 1 == 1 or s[-1] == '(' or s[0] == ')':
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	sequence = input()
	if len(sequence) % 2 == 1 or sequence[0] == ')' or sequence[len(sequence) - 1] == '(':
		print('NO')
	else:
		print('YES')


from collections import Counter
sol = []
for test in range(int(input())):
	s = input()
	cnt = Counter(s)
	if s[0] == ')' or s[-1] == '(':
		sol.append('NO')
	elif cnt['?'] == 0:
		if s == '()':
			sol.append('YES')
		else:
			sol.append('NO')
	elif cnt['?'] % 2 == 0:
		sol.append('YES')
	else:
		sol.append('NO')
for r in sol:
	print(r)


t = int(input())
for i in range(t):
	s = input()
	if len(s) % 2 != 0:
		print('NO')
		continue
	index_left = -1
	index_right = -1
	for i in range(len(s)):
		if s[i] == '(':
			index_left = i
		elif s[i] == ')':
			index_right = i
		else:
			continue
	if index_left < index_right:
		print('YES')
	else:
		if len(s) == 2:
			print('NO')
			continue
		l = False
		r = False
		for i in range(index_right):
			if s[i] == '?':
				l = True
				break
		for i in range(index_left + 1, len(s)):
			if s[i] == '?':
				r = True
				break
		if l == True and r == True:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(0, t):
	nb = 0
	nb1 = 0
	s = input()
	n = len(s)
	for i in s:
		if i == '(' or i == ')':
			nb = nb + 1
		elif i == '?':
			nb1 = nb1 + 1
	if s[0] == ')' or s[n - 1] == '(':
		print('NO')
	elif s[n - 1] == '(':
		print('NO')
	elif (nb1 + nb) % 2 != 0:
		print('NO')
	else:
		print('YES')


def solve():
	s = input()
	l = len(s)
	if s[0] == ')' or l % 2 or s[l - 1] == '(':
		print('NO')
	else:
		prev = 1
		for i in range(1, l):
			if s[i] == '?':
				if prev > 0:
					prev -= 1
				else:
					prev += 1
			elif s[i] == '(':
				prev += 1
			else:
				prev -= 1
		if prev:
			print('NO')
		else:
			print('YES')
for _ in range(int(input())):
	solve()


def print_ans(ans):
	if ans:
		print('YES')
	else:
		print('NO')
for test in range(int(input())):
	sequence = str(input())
	l_b = sequence.find('(')
	r_b = sequence.find(')')
	answer = len(sequence) % 2 == 0
	if l_b < r_b:
		pass
	else:
		answer &= r_b > 0 and l_b < len(sequence) - 1
	print_ans(answer)


def fun(s):
	c = 0
	l = []
	if s[0] == '?':
		s = '(' + s[1:]
	if s[-1] == '?':
		s = s[:-1] + ')'
	for i in range(n):
		if s[i] == '(':
			l.append(s[i])
		elif s[i] == '?':
			c += 1
		elif len(l) > 0:
			l.remove('(')
		else:
			c -= 1
			if c < 0:
				return False
	if len(l) == 0:
		if c % 2 == 0:
			return True
		else:
			return False
	elif len(l) == c % 2:
		return True
	else:
		return False
t = int(input())
for _ in range(t):
	s = input().rstrip()
	n = len(s)
	if s[0] == ')' or s[-1] == '(':
		print('NO')
	elif n % 2 != 0:
		print('NO')
	elif fun(s):
		print('YES')
	else:
		print('NO')


def generate(s):
	if len(s) == 1 or s[0] == ')' or s[-1] == '(':
		return 'NO'
	counto = 0
	countc = 0
	countq = 0
	for i in s:
		if i == '(':
			counto += 1
		if i == ')':
			countc += 1
		if i == '?':
			countq += 1
	if counto > countc:
		if counto == countc + countq:
			return 'YES'
		else:
			return 'NO'
	if counto < countc:
		if counto + countq == countc:
			return 'YES'
		else:
			return 'NO'
	if counto == countc and countq % 2 == 0:
		return 'YES'
	else:
		return 'NO'
t = int(input())
ans = []
for _ in range(t):
	s = list(input())
	ans.append(generate(s))
for i in range(t):
	print(ans[i])


for _ in range(int(input())):
	s = input()
	if s[0] == ')':
		print('NO')
	else:
		bal = 0
		op = 0
		for i in range(len(s)):
			if s[i] == '(':
				bal += 1
				op = 1
			elif s[i] == ')':
				bal -= 1
				op = 0
			else:
				op = 0
				if bal > 0:
					bal -= 1
				else:
					bal += 1
		if bal & 1 == 0 and op == 0:
			print('YES')
		else:
			print('NO')


for ___ in range(int(input())):
	s = input()
	if len(s) % 2 == 0 and s[0] != ')' and (s[-1] != '('):
		print('YES')
	else:
		print('NO')


T = int(input())
seq = []
for i in range(T):
	s = input()
	seq.append(s)
for i in range(T):
	s = seq[i]
	if s[0] != ')' and s[-1] != '(' and (len(s) % 2 == 0):
		half = len(s) // 2
		start = s.count('(')
		end = s.count(')')
		ques = s.count('?')
		if start > half or end > half:
			print('No')
			continue
		print('Yes')
		continue
	print('No')


t = int(input())
for o in range(t):
	s = list(input())
	c = 0
	if len(s) % 2 != 0:
		print('NO')
	elif s[0] == ')':
		print('NO')
	elif s[len(s) - 1] == '(':
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	a = input()
	s = []
	for i in a:
		if i == '(':
			s.append(i)
		elif i == ')':
			if not len(s):
				s.append(i)
			elif s[-1] == '(':
				s.pop()
			else:
				s.insert(0, i)
	print(['NO', 'YES'][(a.count('?') + len(s)) % 2 == 0 and a[0] != ')' and (a[-1] != '(')])


def solve(s):
	c = t = 0
	for i in s:
		if i == '(':
			c += 1
		elif i == ')':
			c -= 1
		else:
			t += 1
		if c + t < 0:
			return False
	return True
for _ in range(int(input())):
	s = input()
	s2 = s[::-1].replace('(', '~').replace(')', '(').replace('~', ')')
	if len(s) % 2:
		print('NO')
		continue
	if solve(s) and solve(s2):
		print('YES')
	else:
		print('NO')


def Valid(s):
	return len(s) % 2 == 0 and s[0] != ')' and (s[-1] != '(')
t = int(input())
for _ in range(t):
	s = input().strip()
	if Valid(s):
		print('YES')
	else:
		print('NO')


testcase = int(input())
while testcase:
	seq = input()
	if len(seq) % 2 != 0 or seq[0] == ')' or seq[-1] == '(':
		print('NO')
	elif seq.count('(') == seq.count(')'):
		print('YES')
	else:
		print('NO')
	testcase -= 1


testcase = int(input())
for t in range(testcase):
	c = input()
	a = 0
	b = 0
	flag = 0
	l = len(c)
	if l % 2 == 1:
		print('NO')
		flag = 1
	else:
		if c[0] == ')' or c[l - 1] == '(':
			print('NO')
			flag = 1
		if flag == 0:
			print('YES')


for _ in range(int(input())):
	s = input()
	if len(s) & 1 or s[0] == ')' or s[-1] == '(':
		print('NO')
	else:
		print('YES')


numoftestcases = int(input())
for duncare in range(numoftestcases):
	string = input()
	if len(string) % 2 == 1:
		print('NO')
	else:
		listofindex = list()
		index1 = string.index('(')
		index2 = string.index(')')
		if index1 < index2:
			print('YES')
		elif index1 == len(string) - 1 or index2 == 0:
			print('NO')
		else:
			print('YES')


import sys
import bisect as bi
import math
from collections import defaultdict as dd
import queue
import heapq
import itertools
input = sys.stdin.readline
import random
mo = 10 ** 9 + 7

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input().strip()

def inin():
	return int(input())
for _ in range(inin()):
	s = sin()
	f = 0
	n = len(s)
	op = s.index('(')
	cl = s.index(')')
	if op < cl:
		c1 = s.count('?')
		c1 += 2
		if c1 % 2:
			f = 1
	else:
		c1 = s.count('?')
		c1 += 2
		if c1 % 2 or op == n - 1 or cl == 0:
			f = 1
	if f:
		print('NO')
	else:
		print('YES')


test_cases = int(input())

def handle_test_case():
	line = input()
	if len(line) % 2 == 1:
		return 'NO'
	score = 0
	buffer = 0
	for char in line:
		if char == ')':
			score -= 1
		elif char == '(':
			score += 1
		else:
			buffer += 1
		if score < 0:
			if buffer == 0:
				return 'NO'
			else:
				buffer -= 1
				score += 1
	new_score = 0
	new_buffer = 0
	for i in range(len(line) - 1, -1, -1):
		char = line[i]
		if char == '(':
			new_score += 1
		elif char == ')':
			new_score -= 1
		else:
			new_buffer += 1
		if new_score > 0:
			if new_buffer == 0:
				return 'NO'
			else:
				new_buffer -= 1
				new_score -= 1
	return 'YES'
for _ in range(test_cases):
	print(handle_test_case())


import sys
import math
from collections import defaultdict
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write()
	pass

def solve(s):
	if len(s) % 2 == 1:
		return 'NO'
	elif s[0] == ')' or s[-1] == '(':
		return 'NO'
	else:
		return 'YES'

def readinput():
	tc = getInt()
	for _ in range(tc):
		s = getString()
		print(solve(s))
readinput()


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	string = input()
	if len(string) & 1:
		return False
	if string[0] == ')' or string[-1] == '(':
		return False
	return True
for _ in range(int(input())):
	print('YES') if solve() else print('NO')


for _ in range(int(input())):
	s = input()
	final = ''
	if len(s) % 2 == 1:
		print('NO')
		continue
	su = 0
	totall = len(s) // 2
	totalr = totall
	for item in s:
		if item == '(':
			totall -= 1
		elif item == ')':
			totalr -= 1
	for i in range(len(s)):
		if s[i] == '?':
			if totall > 0:
				totall -= 1
				final += '('
			else:
				totalr -= 1
				final += ')'
		elif s[i] == '(':
			final += '('
		else:
			final += ')'
	for item in final:
		if su < 0:
			break
		if item == '(':
			su += 1
		else:
			su -= 1
	if su == 0:
		print('YES')
	else:
		print('NO')


from math import *
from collections import deque
from copy import deepcopy
import sys

def inp():
	return sys.stdin.readline().rstrip('\r\n')

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

def strmulti():
	return map(str, inp().split())

def lis():
	return list(map(int, inp().split()))

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def stringlis():
	return list(map(str, inp().split()))

def out(var):
	sys.stdout.write(str(var))

def printlist(a):
	print(' '.join((str(a[i]) for i in range(len(a)))))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
t = int(inp())
for _ in range(t):
	s = list(inp())
	count = 0
	if s[0] == ')' or s[-1] == '(':
		print('NO')
		continue
	if len(s) % 2 == 0:
		print('YES')
	else:
		print('NO')


import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	s = input()
	n = len(s)
	ind = s.index('(')
	ind1 = s.index(')')
	if ind < ind1:
		if (n - 2) % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif ind1 > 0 and ind < n - 1 and ((n - 2) % 2 == 0):
		print('YES')
	else:
		print('NO')


def solve():
	a = list(input())
	ans = 'YES'
	if len(a) % 2 != 0:
		ans = 'NO'
	elif a[0] == ')' or a[-1] == '(':
		ans = 'NO'
	else:
		ans = 'YES'
	print(ans)
for i in range(int(input())):
	solve()


import sys, math
input = sys.stdin.readline
t = int(input())
for tttt in range(t):
	a = input().strip('\n')
	n = len(a)
	count = 0
	for i in a:
		if i == '?':
			count += 1
	x = 0
	y = 0
	for i in range(n):
		if a[i] == '(':
			x = i
		if a[i] == ')':
			y = i
	if count % 2 == 0:
		if y > x:
			print('YES')
		elif x + 1 < n and y - 1 >= 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for s in [*open(0)][1:]:
	print('NYOE S'[len(s) & (s[0] != ')' and '(' < s[-2])::2])


for t in range(int(input())):
	s = input().strip()
	if len(s) % 2 == 1:
		print('No')
	elif s[0] == ')' or s[-1] == '(':
		print('No')
	else:
		h = {}
		h[0] = True
		(n, q) = (0, 0)
		for v in s:
			nh = {}
			if v == '(':
				for k in h.keys():
					nh[k + 1] = True
			elif v == ')':
				for k in h.keys():
					if k > 0:
						nh[k - 1] = True
			else:
				for k in h.keys():
					nh[k + 1] = True
					if k > 0:
						nh[k - 1] = True
			h = nh
		if 0 in h:
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	lis = str(input())
	if len(lis) % 2 != 0 or lis[0] == ')' or lis[-1] == '(':
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	s = input()
	a = s.find('(')
	b = s.find(')')
	if len(s) % 2 == 1:
		print('NO')
	elif a < b:
		print('YES')
	elif b != 0 and a != len(s) - 1:
		print('YES')
	else:
		print('NO')


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
t = int(input())
for tt in range(t):
	s = input()
	s_l = len(s)
	if s_l % 2 == 1:
		print('NO')
		continue
	inx1 = s.index('(')
	inx2 = s.index(')')
	if inx2 == 0 or inx1 == s_l - 1:
		print('NO')
	else:
		print('YES')


def solve(string):
	spaces = string.count('?')
	opens = string.count('(')
	closes = string.count(')')
	n = (spaces - opens + closes) / 2
	if n % 1 != 0:
		return False
	string = string.replace('?', '(', int(n))
	string = string.replace('?', ')')
	depth = 0
	for e in string:
		if e == '(':
			depth += 1
		else:
			if depth == 0:
				return False
			depth -= 1
	return depth == 0
for _ in range(int(input())):
	s = input()
	print('YES' if solve(s) else 'NO')


t = int(input())
for z in range(t):
	n = list(input())
	if len(n) % 2 != 0:
		print('NO')
	else:
		for i in range(len(n)):
			if n[i] == '(':
				ind1 = i
			elif n[i] == ')':
				ind2 = i
		if ind1 < ind2 or (ind1 != len(n) - 1 and ind2 != 0):
			print('YES')
		else:
			print('NO')


import sys
input = sys.stdin.readline

def solve():
	s = input().strip()
	n = len(s)
	left = right = 0
	for i in range(n):
		if s[i] == '(':
			left = i
		elif s[i] == ')':
			right = i
	if left < right:
		return 'YES' if n % 2 == 0 else 'NO'
	else:
		(a, b, c) = (right, left - right - 1, n - 1 - left)
		if a == 0:
			return 'NO'
		elif a % 2 == 0:
			if b % 2 and c % 2:
				return 'YES'
			elif b % 2 == 0 and c >= 2 and (c % 2 == 0):
				return 'YES'
			else:
				return 'NO'
		if b % 2:
			return 'YES' if c >= 2 and c % 2 == 0 else 'NO'
		else:
			return 'YES' if c % 2 else 'NO'
for _ in range(int(input())):
	print(solve())


test_cases = int(input())
for t in range(test_cases):
	in_sequence = input()
	if len(in_sequence) % 2 != 0 or in_sequence[0] == ')' or in_sequence[-1] == '(':
		print('NO')
	else:
		print('YES')


from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
if sys.version_info[0] < 3:
	from io import BytesIO as stream
else:
	from io import StringIO as stream

def sync_with_stdio(sync=True):
	global input, flush
	if sync:
		flush = sys.stdout.flush
	else:
		sys.stdin = stream(sys.stdin.read())
		input = lambda : sys.stdin.readline().rstrip('\r\n')
		sys.stdout = stream()
		register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
for _ in range(int(input())):
	s = list(input())
	l = len(s)
	if l % 2 != 0 or s[0] == ')' or s[-1] == '(':
		print('NO')
	else:
		print('YES')


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(nmbr()):
	s = input()
	n = len(s)
	if n & 1:
		print('NO')
		continue
	p0 = s.find('(')
	p1 = s.find(')')
	if p0 < p1:
		print('YES')
	elif '?' in s[:p1] and '?' in s[p0 + 1:]:
		print('YES')
	else:
		print('NO')


tc = int(input())
for i in range(tc):
	x = input()
	if len(x) % 2 == 1 or x[0] == ')' or x[-1] == '(':
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	stack = []
	string = list(input())
	result = 0
	what = 0
	for s in string:
		if s == '(':
			result += 1
		elif s == ')':
			result -= 1
			if result < 0:
				if what > 0:
					what -= 1
					result += 1
		else:
			what += 1
	val = what - result
	if string[0] != ')' and string[-1] != '(' and (val >= 0) and (not val & 1) and (result >= 0):
		print('YES')
	else:
		print('NO')


def isvalid(s):
	if s[0] == ')':
		return False
	if s[-1] == '(':
		return False
	if s.count('?') % 2 != 0:
		return False
	return True
n = int(input())
for _ in range(n):
	s = str(input())
	if isvalid(s):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = list(input())
	open = a.count('(')
	close = a.count(')')
	que = a.count('?')
	if len(a) % 2 == 1:
		print('NO')
		continue
	opentot = len(a) // 2
	closetot = len(a) // 2
	if opentot < open:
		print('NO')
		continue
	if closetot < close:
		print('NO')
		continue
	openleft = opentot - open
	closeleft = closetot - close
	for j in range(len(a)):
		if openleft and a[j] == '?':
			a[j] = '('
			openleft -= 1
		elif closeleft and a[j] == '?':
			a[j] = ')'
			closeleft -= 1
	counter = 0
	answer = 1
	for j in a:
		if j == '(':
			counter += 1
		elif j == ')':
			counter -= 1
			if counter < 0:
				answer = 0
	if counter:
		answer = 0
	if answer:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	str = input()
	if len(str) % 2 != 0 or str.endswith('('):
		print('NO')
		continue
	if str.startswith('?') or str.startswith('('):
		print('YES')
		continue
	print('NO')


n = int(input())
for _ in range(n):
	l = input()
	if len(l) % 2 == 0:
		if l[0] == ')':
			print('NO')
		elif l[len(l) - 1] == '(':
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


def solve():
	word = str(input())
	if len(word) % 2 != 0:
		print('no')
		return
	(s, qs) = (0, 0)
	for i in range(len(word)):
		if word[i] == '(':
			s += 1
		elif word[i] == ')':
			s -= 1
		else:
			qs += 1
		if s < 0 and qs < abs(s):
			print('no')
			return
	(s, qs) = (0, 0)
	for i in range(len(word) - 1, -1, -1):
		if word[i] == '(':
			s -= 1
		elif word[i] == ')':
			s += 1
		else:
			qs += 1
		if s < 0 and qs < abs(s):
			print('no')
			return
	print('yes')
t = int(input())
while t:
	t -= 1
	solve()


for _ in range(int(input())):
	t = input()
	n = len(t)
	k = n - 2
	d = 0
	ans = True
	for c in t:
		x = c
		if c == '?':
			x = '(' if k > n - 2 >> 1 else ')'
			k -= 1
		d += 1 if x == '(' else -1
		if d < 0:
			ans = False
	ans &= d == 0
	print('YES' if ans else 'NO')


Input = int(input())
for i in range(Input):
	Input2 = input()
	First_Pos = Input2[0]
	Last_Pos = Input2[-1]
	Con_len = len(Input2)
	if First_Pos == ')' or Con_len % 2 != 0 or Last_Pos == '(':
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	string = input()
	if len(string) % 2 != 0:
		print('NO')
	elif string[0] == ')' or string[-1] == '(':
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	s = input()
	if len(s) % 2 != 0:
		print('NO')
		continue
	o = s.find('(')
	c = s.find(')')
	if o < c:
		print('YES')
	elif c > 0 and o < len(s) - 1:
		print('YES')
	else:
		print('NO')


for s in [*open(0)][1:]:
	print('YNEOS'[len(s) & 1 ^ 1 or ')' == s[0] or '(' == s[-2]::2])


t = int(input())
for s in range(t):
	s = input()
	l = list(s)
	flag = 0
	if l[0] == ')' or l[len(l) - 1] == '(':
		print('NO')
	elif len(l) % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in ' ' * int(input()):
	s = input()
	print('YES' if not len(s) & 1 and s[0] != ')' and (s[-1] != '(') else 'NO')


t = int(input())
for _ in range(t):
	s = input()
	a = 0
	b = 0
	c = 0
	f = 1
	for i in range(len(s)):
		if s[i] == '(':
			a += 1
		elif s[i] == ')':
			a -= 1
		else:
			c += 1
		if a < c and c != 0:
			t = c - a
			a += t
			c -= t
		if a < 0:
			f = 0
			break
	if f == 0:
		print('NO')
	elif a == c:
		print('YES')
	elif a == 0 and c % 2 == 0:
		print('YES')
	else:
		print('NO')


n = int(input())

def solve(x):
	if len(x) % 2 == 1:
		return 'NO'
	if x[0] == ')' or x[-1] == '(':
		return 'NO'
	return 'YES'
for _ in range(n):
	print(solve(input()))


t = int(input())
count1 = 0
count2 = 0
for i in range(t):
	inp = input()
	for el in inp:
		if el == '(':
			count1 = count1 + 1
		elif el == ')':
			count1 = count1 - 1
		elif el == '?':
			count2 = count2 + 1
	if count1 + count2 % 2 == 0 and inp[-1] != '(' and (inp[0] != ')'):
		print('YES')
	else:
		print('NO')
	count1 = 0
	count2 = 0


t = int(input())
for _ in range(t):
	s = input()
	x = s.index('(')
	y = s.index(')')
	if len(s) % 2 != 0:
		print('NO')
	elif s[0] == ')':
		print('NO')
	elif s[len(s) - 1] == '(':
		print('NO')
	else:
		print('YES')


def valid_brackets(s):
	openBrackets = 0
	for i in s:
		if openBrackets < 0:
			return False
		if i == '(':
			openBrackets += 1
		elif i == ')':
			openBrackets -= 1
	if openBrackets != 0:
		return False
	return True
t = int(input())
for _ in range(t):
	s = input()
	a = list(s)
	count = len(s) // 2 - 1
	for i in range(len(s)):
		if a[i] == '?':
			if count > 0:
				a[i] = '('
				count -= 1
			else:
				a[i] = ')'
	if valid_brackets(str(a)):
		print('YES')
	else:
		print('NO')


a = int(input())
for i in range(a):
	b = input()
	if b[0] == ')' or b[-1] == '(':
		print('NO')
	elif b.count('(') == b.count(')') and b.count('?') == 0:
		print('YES')
	elif b.count('(') == b.count(')') and b.count('?') % 2 == 0:
		print('YES')
	elif b.count('(') == b.count(')') and b.count('?') % 2 != 0:
		print('NO')
	elif b.count('?') == max(b.count('('), b.count(')')) - min(b.count('('), b.count(')')):
		print('YES')
	else:
		print('NO')


def solve():
	s = input().rstrip()
	if len(s) % 2 == 1:
		print('NO')
		return
	i = 0
	count = 0
	pos = True
	arr = []
	for i in range(len(s)):
		if s[i] in ['(', ')']:
			arr.append(count)
			arr.append(s[i])
			count = 0
		else:
			count += 1
	arr.append(count)
	if arr[1] == '(':
		print('YES')
		return
	else:
		if arr[0] == 0 or arr[4] == 0:
			print('NO')
			return
		if arr[0] % 2 == 1:
			print('YES')
			return
		elif arr[2] > 0:
			print('YES')
			return
		elif arr[4] > 1:
			print('YES')
			return
		print('NO')
		return

def main():
	T = int(input())
	for c in range(T):
		solve()
main()