You have been assigned to develop a filter for bad messages in the in-game chat. A message is a string $S$ of length $n$, consisting of lowercase English letters and characters ')'. The message is bad if the number of characters ')' at the end of the string strictly greater than the number of remaining characters. For example, the string ")bc)))" has three parentheses at the end, three remaining characters, and is not considered bad.


-----Input-----

The first line contains the number of test cases $t$ ($1 \leq t \leq 100$). Description of the $t$ test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 100$). The second line of each test case contains a string $S$ of length $n$, consisting of lowercase English letters and characters ')'.


-----Output-----

For each of $t$ test cases, print "Yes" if the string is bad. Otherwise, print "No".

You can print each letter in any case (upper or lower).


-----Examples-----

Input
5
2
))
12
gl))hf))))))
9
gege)))))
14
)aa))b))))))))
1
)
Output
Yes
No
Yes
Yes
Yes


-----Note-----

None

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
tests = int(input())
for test in range(tests):
	n = int(input())
	S = input()
	i = n - 1
	brackets_count = 0
	while i >= 0:
		if S[i] == ')':
			brackets_count += 1
		else:
			break
		i -= 1
	if brackets_count > n - brackets_count:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	r = int(input())
	a = list(map(str, input().split()))
	listlid = []
	count = 0
	for j in a:
		listlid += j
	for x in range(r - 1, -1, -1):
		if listlid[x] != ')':
			break
		count += 1
	ost = r - count
	if ost >= count:
		print('No')
	else:
		print('Yes')


t = int(input())
for k in range(0, t, 1):
	n = int(input())
	s = input()
	count = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			count = count + 1
		else:
			break
	if count > len(s) - count:
		print('Yes')
	else:
		print('No')


k = int(input())
for _ in range(k):
	input()
	s = input()
	n = 0
	for c in s[::-1]:
		if c != ')':
			break
		n += 1
	if n > len(s) - n:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	i = n - 1
	while i >= 0:
		if s[i] != ')':
			break
		c += 1
		i -= 1
	if c > n - c:
		print('Yes')
	else:
		print('No')


t = int(input())
while t:
	n = int(input())
	s = input()
	s = s[::-1]
	count = 0
	for i in s:
		if i == ')':
			count += 1
		else:
			break
	if count > n // 2:
		print('Yes')
	else:
		print('No')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	for i in s[::-1]:
		if i == ')':
			count += 1
		else:
			break
	if count > n / 2:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	s = input()
	temp = []
	for j in s[-1::-1]:
		if j != ')':
			break
		else:
			temp.append(j)
	if len(temp) > len(s) - len(temp):
		print('Yes')
	else:
		print('No')


t = int(input())
pos = []
data = []
i = 0
while i != t:
	pos.append(int(input()))
	data.append(input()[::-1])
	i += 1
for i in range(t):
	if data[i].count(')') != pos[i]:
		k = 0
		while data[i][k] == ')':
			if data[i][k] != ')':
				break
			k += 1
		if pos[i] - k < k:
			print('Yes')
		else:
			print('No')
	else:
		print('Yes')
		continue


t = int(input())
if t >= 1 and t <= 100:
	for i in range(t):
		x = 0
		n = int(input())
		s = input()
		if (n >= 1 and n <= 100) and len(s) == n:
			for i in range(len(s) - 1, -1, -1):
				if ord(s[i]) == 41 or (ord(s[i]) >= 97 and ord(s[i]) <= 122):
					if ord(s[i]) != 41:
						break
					else:
						x += 1
		a = len(s) - x
		if x > a:
			print('Yes')
		else:
			print('No')


n = int(input())
a = []
for i in range(n):
	nu = int(input())
	for k in range(nu):
		s = input('').lower()
		a.append(s)
		if len(s) == nu:
			break
for z in a:
	t = []
	v = []
	for i in range(len(z) - 1, -1, -1):
		if 97 <= ord(z[i]) <= 122:
			break
		else:
			t.append(z[i])
	for i in t:
		if i == ')':
			v.append(i)
	c = len(z) - len(v)
	if c >= len(v):
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	l = int(input())
	user = input()
	user = user[::-1]
	if user[0] == ')':
		got = 0
		p_count = 0
		ch_count = 0
		for i in user:
			if got == 0:
				if i == ')':
					p_count += 1
				else:
					got = 1
					ch_count += 1
			else:
				ch_count += 1
		if p_count > ch_count:
			print('Yes')
		elif l == p_count:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	s = input()[::-1]
	if set(s) == {')'}:
		print('Yes')
	else:
		for i in range(len(s)):
			if s[i] != ')':
				if n / (n - i) > 2:
					print('Yes')
				else:
					print('No')
				break


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = s.rstrip(')')
	print('Yes' if n - len(t) > len(t) else 'No')


for s in [*open(0)][2::2]:
	print('YNeos'[{*s[len(s) // 2 - 1:-1]} != {')'}::2])


for _ in range(int(input())):
	n = int(input())
	s = input()
	start = -1
	total = 0
	for i in range(n):
		if s[i] != ')':
			start = -1
			total = 0
		else:
			if start == -1:
				start = i
			total += 1
	print('Yes' if total > len(s[:start]) else 'No')


ates = int(input())
li = []
tr = ates * 2
ki = []
for i in range(tr):
	if i % 2 == 1:
		li.append(input())
	else:
		ki.append(input())
for i in li:
	b = i[::-1]
	d = 0
	for i in b:
		if i == ')':
			d += 1
		else:
			break
	if d > len(b) - d:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n_ = input()
	s = input()
	l = len(s)
	i = 1
	count = 0
	flag = True
	while i <= l and flag:
		if s[-1 * i] == ')':
			count += 1
		else:
			flag = False
		if count > l / 2:
			flag = False
		i += 1
	if count > l / 2:
		print('Yes')
	else:
		print('No')


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	i = len(s) - 1
	cnt = 0
	while i >= 0 and s[i] == ')':
		cnt += 1
		i -= 1
	if cnt > n - cnt:
		print('Yes')
	else:
		print('No')


for i in range(int(input())):
	b = int(input())
	a = input()
	b = a[::-1]
	s = 0
	for j in range(len(b)):
		if b[j] != ')':
			break
		s += 1
	if len(a) - s >= len(a) / 2:
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	bad = 0
	for j in range(n - 1, -1, -1):
		if s[j] != ')':
			break
		bad += 1
	good = len(s) - bad
	if bad > good:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	idx = 0
	for i in reversed(range(n)):
		if s[i] != ')':
			idx = i + 1
			break
	if n - idx > idx:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	x = int(input())
	y = input()
	z = []
	for i in range(x):
		if y[i].isalpha():
			z.append(i)
	if len(z) == 0:
		print('Yes')
	else:
		d = max(z)
		e = y[d + 1:]
		f = y[:d + 1]
		r = e.count(')')
		if r > x // 2:
			print('Yes')
		else:
			print('No')


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	i = -1
	while -1 * i <= n and s[i] == ')':
		i -= 1
	i += 1
	if -i > n + i:
		print('Yes')
	else:
		print('No')


t = int(input())
lan = []
for _ in range(t):
	n = int(input())
	s = list(input())
	ctr = 0
	for indx in range(1, n + 1):
		if s[-indx] == ')':
			ctr += 1
		else:
			break
	if ctr > n - ctr:
		lan.append('Yes')
	else:
		lan.append('No')
print(*lan, sep='\n')


test = int(input())
for i in range(test):
	c = 0
	l = int(input())
	s = input()
	s = s[-1::-1]
	for j in range(0, l):
		if s[j] == ')':
			c += 1
		else:
			break
	if c > l - c:
		print('Yes')
	else:
		print('No')


x = int(input())
for j in range(x):
	len = int(input())
	s = input()
	c = 0
	for i in range(len):
		if s[-(i + 1)] == ')':
			c += 1
		elif s[-i] != ')':
			break
	if c > len - c:
		print('Yes')
	else:
		print('No')
	c = 0


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	j = n - 1
	scobe = 0
	while j >= 0:
		if s[j] == ')':
			scobe += 1
		else:
			break
		j -= 1
	if scobe > n - scobe:
		print('Yes')
	else:
		print('No')


from cmath import *
from math import *
from decimal import *
from collections import *
import numbers
from operator import index
import sys

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

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

def _int():
	return int(input())

def solves():
	n = int(input())
	s = list(input())
	indx = 0
	for i in range(n - 1, -1, -1):
		if s[i] == ')':
			indx += 1
		else:
			break
	if n - indx < indx:
		print('Yes')
	else:
		print('No')
t = 1
t = int(input())
for _ in range(0, t):
	solves()


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = s.rstrip(')')
	p = len(s) - len(x)
	if p > len(x):
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	c = 0
	for i in list(input())[::-1]:
		if i == ')':
			c += 1
		else:
			break
	print('Yes') if c > n - c else print('No')


for i in range(int(input())):
	n = int(input())
	x = len(input().rstrip(')'))
	if n - x > x:
		print('Yes')
	else:
		print('No')


t = int(input())
test_cases = []
for i in range(1, 2 * t + 1, 2):
	n = int(input())
	s = input()
	test_cases.append((n, s))
results = []
for (n, s) in test_cases:
	num_end_parentheses = len(s) - len(s.rstrip(')'))
	num_remaining_chars = len(s.rstrip(')'))
	if num_end_parentheses > num_remaining_chars:
		results.append('Yes')
	else:
		results.append('No')
print('\n'.join(results))


for _ in range(int(input())):
	n = int(input())
	s = input()
	cp = 0
	for c in s:
		if c == ')':
			cp += 1
		else:
			cp = 0
	print('Yes' if cp > n - cp else 'No')


for i in range(int(input())):
	n = int(input())
	s = input()
	se = s.rstrip(')')
	if len(s) - len(se) > len(se):
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	str = s[::-1]
	cnt = 0
	for i in range(len(str)):
		if str[i] == ')':
			cnt += 1
		else:
			break
	if len(s) - cnt < cnt:
		print('Yes')
	else:
		print('No')


def func(A):
	i = len(A) - 1
	count = 0
	while i >= 0 and A[i] == ')':
		count += 1
		i -= 1
	if count > len(A) - count:
		print('Yes')
	else:
		print('No')
x = int(input())
a = []
for _ in range(x):
	n = int(input())
	a.append(input())
for i in a:
	func(i)


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		s = input()
		count = 0
		for i in range(n - 1, -1, -1):
			if s[i] == ')':
				count += 1
			else:
				break
		if 2 * count > n:
			print('Yes')
		else:
			print('No')
main()


t = int(input())
for i in range(t):
	c = 0
	n = int(input())
	s = input()
	if n == 1:
		if s == ')':
			print('Yes')
			continue
		else:
			print('No')
			continue
	if n == 2:
		if s[0] == ')' and s[1] == ')':
			print('Yes')
			continue
		else:
			print('No')
			continue
	for j in range(n - 1, 0, -1):
		if s[j] == ')':
			c = c + 1
		else:
			break
	if c > n - c:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	s = input()[::-1]
	res = n
	for (i, val) in enumerate(s):
		if not val == ')':
			res = i
			break
	print('Yes' if res > n // 2 else 'No')


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for j in range(n - 1, -1, -1):
		if s[j] == ')':
			c += 1
		else:
			break
	x = n - c
	if c > x:
		print('Yes', end='\n')
	else:
		print('No', end='\n')


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	s = input()
	s = s[::-1]
	c = 0
	for i in range(n):
		if s[i] == ')':
			c += 1
		else:
			break
	if c > n - c:
		ans.append('Yes')
	else:
		ans.append('No')
for i in ans:
	print(i)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	g = 0
	if s.count(')') == n:
		print('Yes')
	else:
		for i in s[::-1]:
			if i == ')':
				c += 1
				index = s.index(i)
			else:
				break
		g = n - c
		if g < c:
			print('Yes')
		else:
			print('No')


test_cases = int(input())
for i in range(test_cases):
	len_string = int(input())
	string = input()
	rev_string = string[::-1]
	count = 0
	j = 0
	k = 1
	while rev_string[j:k] == ')':
		j += 1
		k += 1
		count += 1
	rem_ch = len_string - count
	if count > rem_ch:
		print('Yes')
	else:
		print('No')


n = int(input())
for i in range(n):
	sum = 0
	leng = int(input())
	word = input()
	word = list(word)
	for j in range(leng - 1, -1, -1):
		if word[j] == ')':
			sum = sum + 1
		else:
			break
	if sum <= leng - sum:
		print('No')
	else:
		print('Yes')