A valid parentheses sequence is a non-empty string where each character is either '(' or ')', which satisfies the following constraint:

You can find a way to repeat erasing adjacent pairs of parentheses '()' until it becomes empty.

	For example, '(())' and '()((()()))' are valid parentheses sequences, but ')()(' and '(()' are not.

	Mike has a valid parentheses sequence. He really likes everything about his sequence, except the fact that it is quite long. So Mike has recently decided that he will replace his parentheses sequence with a new one in the near future. But not every valid parentheses sequence will satisfy him. To help you understand his requirements we'll introduce the pseudocode of function F(S):

	FUNCTION F( S - a valid parentheses sequence )
	BEGIN
		balance = 0
		max_balance = 0
		FOR index FROM 1 TO LENGTH(S)
		BEGIN
			if S[index] == '(' then balance = balance + 1
			if S[index] == ')' then balance = balance - 1
			max_balance = max( max_balance, balance )
		END
		RETURN max_balance
	END

	In other words, F(S) is equal to the maximal balance over all prefixes of S.

	Let's denote A as Mike's current parentheses sequence, and B as a candidate for a new one. Mike is willing to replace A with B if F(A) is equal to F(B). He would also like to choose B with the minimal possible length amongst ones satisfying the previous condition. If there are several such strings with the minimal possible length, then Mike will choose the least one lexicographically, considering '(' to be less than ')'.

	Help Mike!

-----Input-----

	The first line of the input contains one integer T denoting the number of testcases to process.

	The only line of each testcase contains one string A denoting Mike's parentheses sequence. It is guaranteed that A only consists of the characters '(' and ')'. It is also guaranteed that A is a valid parentheses sequence.

-----Output-----

	The output should contain exactly T lines, one line per each testcase in the order of their appearance. The only line of each testcase should contain one string B denoting the valid parentheses sequence that should be chosen by Mike to replace A.

-----Constraints-----
1 ≤ T ≤ 5;
1 ≤ |A| ≤ 100000(105).

-----Example-----
Input:
1
()((()()))

Output:
((()))

Source: codechef | Difficulty: EASY
Tags: Greedy algorithms


Solutions:
for i in range(int(input())):
	s = input()
	m = 0
	c = 0
	for j in range(len(s)):
		if s[j] == '(':
			c += 1
		elif s[j] == ')':
			c -= 1
		m = max(m, c)
	print(m * '(' + m * ')')


for _ in range(int(input())):
	s = input()
	max_count = 0
	bal = 0
	for i in s:
		if i == ')':
			bal = bal - 1
		else:
			bal = bal + 1
		max_count = max(max_count, bal)
	ans = ''
	for i in range(0, max_count):
		ans += '('
	for i in range(0, max_count):
		ans += ')'
	print(ans)


for _ in range(int(input())):
	a = input()
	balance = 0
	max_balance = 0
	for i in range(len(a)):
		if a[i] == '(':
			balance += 1
		if a[i] == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	for i in range(max_balance):
		print('(', end='')
	for i in range(max_balance):
		print(')', end='')
	print()


def max_brac(s):
	(bal, max_bal) = (0, 0)
	for z in range(len(s)):
		if s[z] == '(':
			bal += 1
		elif s[z] == ')':
			bal -= 1
		max_bal = max(max_bal, bal)
	print('(' * max_bal + ')' * max_bal)
t = int(input())
for i in range(t):
	s = input()
	max_brac(s)


t = int(input())

def F(a):
	balance = 0
	max_balance = 0
	for i in range(len(a)):
		if a[i] == '(':
			balance += 1
			max_balance = max(max_balance, balance)
		elif a[i] == ')':
			balance -= 1
	return max_balance
for i in range(t):
	a = input()
	f = F(a)
	print('(' * f + ')' * f)


for _ in range(int(input())):
	S = input()
	s = ''
	balance = 0
	maxbal = 0
	for i in range(len(S)):
		if S[i] == '(':
			balance += 1
		else:
			balance -= 1
		maxbal = max(maxbal, balance)
	for i in range(maxbal):
		s += '('
	for i in range(maxbal):
		s += ')'
	print(s)


for _ in range(int(input())):
	a = input()
	balance = 0
	max_balance = 0
	for i in a:
		if i == '(':
			balance += 1
		if i == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	res = ''
	for i in range(max_balance):
		res += '('
	for i in range(max_balance):
		res += ')'
	print(res)


tu = int(input())
for iop in range(tu):
	sa = input()
	mp = 0
	cvr = 0
	for jkl in range(len(sa)):
		if sa[jkl] == '(':
			cvr += 1
		elif sa[jkl] == ')':
			cvr -= 1
		mp = max(mp, cvr)
	print(mp * '(' + mp * ')')


try:
	for i in range(int(input())):
		s = input()
		balance = 0
		max_balance = 0
		for i in s:
			if i == '(':
				balance += 1
			else:
				balance -= 1
			max_balance = max(max_balance, balance)
		print('(' * max_balance, ')' * max_balance, sep='')
except Exception as e:
	print(e)


try:

	def F(S):
		balance = 0
		max_balance = 0
		for i in S:
			if i == '(':
				balance += 1
			elif i == ')':
				balance -= 1
			max_balance = max(balance, max_balance)
		return max_balance
	for _ in range(int(input())):
		S = input()
		max_balance = F(S)
		for i in range(max_balance):
			print('(', end='')
		for i in range(max_balance):
			print(')', end='')
		print('')
except:
	pass


for i in range(int(input())):
	s = input()
	maxval = 0
	bal = 0
	for i in range(len(s)):
		if s[i] == '(':
			bal += 1
		else:
			bal -= 1
		maxval = max(maxval, bal)
	print(maxval * '(' + maxval * ')')


for _ in range(int(input())):
	s = input()
	m = 0
	b = 0
	for i in s:
		if i == '(':
			b += 1
		else:
			b -= 1
		m = max(m, b)
	s = ''
	for j in range(m):
		s = '(' + s
		s = s + ')'
	print(s)


for I in range(int(input())):
	s = input()
	b = 0
	mb = 0
	for i in s:
		if i == '(':
			b += 1
		elif i == ')':
			b -= 1
		mb = max(b, mb)
	print('(' * mb + ')' * mb)


for i in range(int(input())):
	s = input()
	c = 0
	mc = 0
	for i in s:
		if i == '(':
			c += 1
		else:
			c -= 1
		mc = max(mc, c)
	print('(' * mc + ')' * mc)


for i in range(int(input())):
	S = input()
	balance = 0
	max_balance = 0
	for i in S:
		if i == '(':
			balance = balance + 1
		else:
			balance = balance - 1
		max_balance = max(max_balance, balance)
	print('(' * max_balance, end='')
	print(')' * max_balance)


for _ in range(int(input())):
	s = input()
	max_bal = 0
	bal = 0
	for i in s:
		if i == '(':
			bal += 1
		else:
			bal -= 1
		max_bal = max(max_bal, bal)
	res = '(' * max_bal
	res += ')' * max_bal
	print(res)


for i in range(int(input())):
	x = input()
	maxlen = 0
	balance = 0
	for i in x:
		if i == '(':
			balance += 1
		else:
			balance -= 1
		maxlen = max(maxlen, balance)
	print('(' * maxlen + ')' * maxlen)


def parenthesis(string):
	min_bracket = total = 0
	for item in string:
		if item == '(':
			total += 1
		else:
			total -= 1
		min_bracket = max(min_bracket, total)
	ans = '(' * min_bracket + ')' * min_bracket
	return ans
for _ in range(int(input())):
	parenth = input()
	print(parenthesis(parenth))


for i in range(int(input())):
	s = input()
	balance = 0
	max_balance = 0
	for i in range(len(s)):
		if s[i] == '(':
			balance += 1
		else:
			balance -= 1
		max_balance = max(balance, max_balance)
	a = ''
	for i in range(max_balance):
		a += '('
	for i in range(max_balance):
		a += ')'
	print(a)


t = int(input())
for x in range(t):
	s = input()
	bal = 0
	maxbal = 0
	for i in s:
		if i == '(':
			bal += 1
		if i == ')':
			bal -= 1
		maxbal = max(maxbal, bal)
	for i in range(maxbal):
		print('(', end='')
	for i in range(maxbal):
		print(')', end='')
	print('\n')


for _ in range(int(input())):
	x = input()
	l = 0
	r = 0
	for i in x:
		if i == '(':
			l += 1
		elif i == ')':
			l -= 1
		r = max(l, r)
	print('(' * r + ')' * r)


def check(string):
	(bal, max_balance) = (0, 0)
	for i in range(len(string)):
		if string[i] == '(':
			bal += 1
		else:
			bal -= 1
		max_balance = max(max_balance, bal)
	return max_balance
for x in range(int(input())):
	string = input()
	ans = check(string)
	print(ans * '(' + ')' * ans)


for i in range(int(input())):
	j = input()
	balance = 0
	max_balance = 0
	for i in range(len(j)):
		if j[i] == '(':
			balance += 1
		if j[i] == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	for i in range(max_balance):
		print('(', end='')
	for i in range(max_balance):
		print(')', end='')
	print()


number_of_testcase = int(input())
for itr in range(number_of_testcase):
	balanced_string = input()
	res = 0
	max_res = 0
	for string_itr in range(len(balanced_string)):
		if balanced_string[string_itr] == '(':
			res = res + 1
		if balanced_string[string_itr] == ')':
			res = res - 1
		max_res = max(max_res, res)
	print('(' * max_res + ')' * max_res)


T = int(input())
for i in range(T):
	A = input()
	b = 0
	mb = 0
	for i in A:
		if i == '(':
			b += 1
		if i == ')':
			b -= 1
		mb = max(b, mb)
	A = '(' * mb + ')' * mb
	print(A)


n = int(input())
for i in range(n):
	x = input()
	maxbal = 0
	bal = 0
	for i in x:
		if i == '(':
			bal = bal + 1
		elif i == ')':
			bal = bal - 1
		maxbal = max(bal, maxbal)
	s = ''
	for i in range(maxbal):
		s = s + '('
	for i in range(maxbal):
		s = s + ')'
	print(s)


t = int(input())
for _ in range(t):
	s = input()
	(b, mx) = (0, 0)
	for ch in s:
		if ch == '(':
			b += 1
		elif ch == ')':
			b -= 1
		mx = max(mx, b)
	print('(' * mx + ')' * mx)


t = int(input())
while t > 0:
	a = input()
	c = 0
	m = 0
	for i in a:
		if i == '(':
			c += 1
		else:
			c -= 1
		m = max(m, c)
	for i in range(m):
		print('(', end='')
	for i in range(m):
		print(')', end='')
	print()
	t -= 1


def F(s):
	balance = 0
	max_balance = 0
	for c in s:
		if c == '(':
			balance += 1
		elif c == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance
t = int(input())
for _ in range(t):
	a = input().strip()
	max_balance = F(a)
	stack = []
	for c in a:
		if not stack or stack[-1] == '(':
			stack.append(c)
		elif stack[-1] == ')' and c == ')':
			stack.append(c)
		else:
			stack.pop()
	b = ''.join(stack)
	print(b)


for _ in range(int(input())):
	s = input()
	(max_brac, brac) = (0, 0)
	for i in range(len(s)):
		if s[i] == '(':
			brac += 1
		elif s[i] == ')':
			brac -= 1
		max_brac = max(max_brac, brac)
	print('(' * max_brac + ')' * max_brac)


for i in range(int(input())):
	s = input()
	bal = 0
	m_bal = 0
	for i in range(len(s)):
		if s[i] == '(':
			bal = bal + 1
		else:
			bal = bal - 1
		m_bal = max(m_bal, bal)
	r = '(' * m_bal
	r = r + ')' * m_bal
	print(r)


t = int(input())
for tc in range(t):
	s = input()
	c = 0
	d = 0
	for j in s:
		if j == '(':
			c += 1
			d = max(d, c)
		else:
			c -= 1
	print('(' * d + ')' * d)


T = int(input())
for i in range(T):
	A = input()
	bal = 0
	max_balance = 0
	for i in A:
		if i == '(':
			bal += 1
		else:
			bal -= 1
		max_balance = max(max_balance, bal)
	for i in range(max_balance):
		print('(', end='')
	for j in range(max_balance):
		print(')', end='')
	print('')


t = int(input())

def Bracket(s):
	balance = 0
	max_balance = 0
	for i in range(len(s) - 1):
		if s[i] == '(':
			balance = balance + 1
		if s[i] == ')':
			balance = balance - 1
		max_balance = max(max_balance, balance)
	s = '(' * max_balance + ')' * max_balance
	return s
for _ in range(t):
	s = input()
	print(Bracket(s))


T = int(input())
for j in range(0, T):
	s = input()
	maxbalance = 0
	balance = 0
	for i in range(len(s)):
		a = s[i]
		if a == '(':
			balance += 1
		else:
			balance -= 1
		if balance > maxbalance:
			maxbalance = balance
	print('(' * maxbalance, ')' * maxbalance, sep='')


import sys

def main():
	a = [None] * 100000
	k = 0
	max_val = 0
	t = int(input())
	for x in range(t):
		a = list(input().strip())
		l = len(a)
		for i in range(l):
			if a[i] == '(':
				k += 1
			else:
				k -= 1
			if max_val < k:
				max_val = k
		for i in range(max_val):
			sys.stdout.write('(')
		while max_val > 0:
			sys.stdout.write(')')
			max_val -= 1
		sys.stdout.write('\n')
main()


T = int(input())
for i in range(0, T):
	A = input()
	bal = 0
	st = ''
	max_bal = 0
	for j in range(0, len(A)):
		if A[j] == '(':
			bal = bal + 1
		else:
			bal -= 1
		max_bal = max(max_bal, bal)
	for k in range(0, max_bal):
		st += '('
	for z in range(0, max_bal):
		st += ')'
	print(st)


def f(S):
	balance = 0
	max_balance = 0
	for i in S:
		if i == '(':
			balance += 1
		if i == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance
for _ in range(int(input())):
	A = input()
	b = f(A)
	S = ''
	for i in range(b):
		S += '('
	for i in range(b):
		S += ')'
	print(S)


for _ in range(int(input())):
	a = input()
	bal = 0
	max_bal = 0
	for i in range(len(a)):
		if a[i] == '(':
			bal += 1
		if a[i] == ')':
			bal -= 1
		max_bal = max(bal, max_bal)
	print('(' * max_bal + ')' * max_bal)


for _ in range(int(input())):
	s = input()
	(c, a) = (0, 0)
	for i in s:
		if i == '(':
			c += 1
			a = max(a, c)
		elif i == ')':
			c -= 1
	print('(' * a + ')' * a)


T = input()
T = int(T)

def main_logic(sentence):
	ctr = 0
	maximum = 0
	ans = ''
	for i in range(len(sentence)):
		if sentence[i] == '(':
			ctr = ctr + 1
		else:
			ctr = ctr - 1
		maximum = max(maximum, ctr)
	for i in range(maximum):
		ans = ans + '('
	for i in range(maximum):
		ans = ans + ')'
	print(ans)
for i in range(T):
	test_case = input()
	main_logic(str(test_case))


def fun(s):
	b = 0
	m = 0
	for i in s:
		if i == '(':
			b += 1
		else:
			b -= 1
		m = max(m, b)
	return m
t = int(input())
for i in range(t):
	s = input()
	x = fun(s)
	for j in range(x):
		print('(', end='')
	for j in range(x):
		print(')', end='')
	print()


for _ in range(int(input())):
	A = input()
	balance = 0
	max_balance = 0
	for i in A:
		if i == '(':
			balance += 1
		elif i == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	print('(' * max_balance + ')' * max_balance)


for _ in range(int(input())):
	b = 0
	mx = 0
	for i in input():
		if i == '(':
			b += 1
		else:
			b -= 1
		mx = max(b, mx)
	print('(' * mx + ')' * mx)


for _ in range(int(input())):
	s = input()
	n = 0
	m = 0
	for i in s:
		if i == '(':
			n += 1
		else:
			n -= 1
		m = max(m, n)
	print('(' * m, end='')
	print(')' * m)


t = int(input())
for _ in range(t):
	s = input()
	(bal, max_bal) = (0, 0)
	for i in range(len(s)):
		if s[i] == '(':
			bal += 1
		elif s[i] == ')':
			bal -= 1
		max_bal = max(max_bal, bal)
	res = ''
	for i in range(max_bal):
		res += '('
	for i in range(max_bal):
		res += ')'
	print(res)


for _ in range(int(input())):
	s = input()
	v = 0
	a = 0
	for i in s:
		if i == '(':
			v = v + 1
		elif i == ')':
			v = v - 1
		a = max(a, v)
	print('(' * a, ')' * a, sep='')


def fun(s):
	bal = 0
	maxbal = 0
	for i in range(len(s)):
		if s[i] == '(':
			bal += 1
		else:
			bal -= 1
		maxbal = max(maxbal, bal)
	return maxbal
t = int(input())
while t > 0:
	s = input()
	maxbal = fun(s)
	print('(' * maxbal + ')' * maxbal)
	t -= 1


for i in range(int(input())):
	s = input()
	b = 0
	mb = 0
	for i in s:
		if i == '(':
			b += 1
		else:
			b -= 1
		mb = max(mb, b)
	print('(' * mb, end='')
	print(')' * mb)


T = int(input())
for i in range(T):
	A = input()
	bal = 0
	max_bal = 0
	for index in range(len(A)):
		if A[index] == '(':
			bal += 1
		if A[index] == ')':
			bal -= 1
		max_bal = max(max_bal, bal)
	new_s = ' '
	for i in range(max_bal):
		new_s += '('
	for j in range(max_bal):
		new_s += ')'
	print(new_s)


q = int(input())
for i in range(q):
	w = str(input())
	r = []
	for i in w:
		r.append(i)
	t = 0
	y = 0
	for i in r:
		if i == '(':
			t = t + 1
		if i == ')':
			t = t - 1
		y = max(y, t)
	u = ''
	for i in range(y):
		u = u + '('
	for i in range(y):
		u = u + ')'
	print(u)


def F(S):
	balance = 0
	max_balance = 0
	for i in S:
		if i == '(':
			balance += 1
		elif i == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance
for _ in range(int(input())):
	S = input()
	max_balance = F(S)
	resStr = '(' * max_balance
	resStr += ')' * max_balance
	print(resStr)


for _ in range(int(input())):
	brackets = input()
	maxb = 0
	c = 0
	for b in brackets:
		if b == '(':
			c += 1
		else:
			c -= 1
		maxb = max(maxb, c)
	print('(' * maxb + ')' * maxb)


def f(s):
	balance = 0
	max_balance = 0
	for i in range(len(s)):
		if s[i] == '(':
			balance += 1
		if s[i] == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance
for t in range(int(input())):
	s = input()
	n = f(s)
	print('(' * n + ')' * n)


for _ in range(int(input())):
	(maxcount, count) = (0, 0)
	s = input()
	for i in s:
		if i == '(':
			count += 1
		else:
			count -= 1
		maxcount = max(maxcount, count)
	print('(' * maxcount + ')' * maxcount)


def fun(s):
	(bal, max_bal) = (0, 0)
	for z in range(len(s)):
		if s[z] == '(':
			bal += 1
		elif s[z] == ')':
			bal -= 1
		max_bal = max(max_bal, bal)
	print('(' * max_bal + ')' * max_bal)
t = int(input())
for _ in range(t):
	s = str(input())
	fun(s)


def Brack(s):
	balance = 0
	max_balance = 0
	for i in range(len(s)):
		if s[i] == '(':
			balance = balance + 1
		elif s[i] == ')':
			balance = balance - 1
		max_balance = max(max_balance, balance)
	return max_balance
for i in range(int(input())):
	s = input()
	k = Brack(s)
	print(k * '(' + k * ')')


def f(p):
	balance = 0
	max_balance = 0
	for x in range(len(p)):
		if p[x] == '(':
			balance += 1
		if p[x] == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance

def user_input():
	for tc in range(int(input())):
		p = input()
		(a, b, c) = ('(', ')', '')
		for i in range(f(p)):
			c = a + c + b
		print(c)
user_input()


for t in range(int(input())):
	s = input()
	(c, a) = (0, 0)
	for i in range(len(s)):
		if s[i] == '(':
			c += 1
		elif s[i] == ')':
			c -= 1
		a = max(a, c)
	print('(' * a + ')' * a)


def f(s):
	balance = 0
	max_balance = 0
	for i in range(len(s)):
		if s[i] == '(':
			balance += 1
		elif s[i] == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance
for _ in range(int(input())):
	s = input()
	max_balance = f(s)
	print('(' * max_balance + ')' * max_balance)


def F(S1):
	bal = 0
	max_bal = 0
	for j in range(0, len(S1)):
		if S1[j] == '(':
			bal += 1
		elif S1[j] == ')':
			bal -= 1
		max_bal = max(max_bal, bal)
	return max_bal
for i in range(int(input())):
	S = input()
	x = F(S)
	for j in range(x):
		print('(', end='')
	for j in range(x):
		print(')', end='')
	print()


def f(s):
	(balance, max_balance) = (0, 0)
	for i in s:
		if i == '(':
			balance += 1
		elif i == ')':
			balance -= 1
		max_balance = max(balance, max_balance)
	return max_balance
t = int(input())
while t > 0:
	s = input()
	f_score = f(s)
	print('(' * f_score + ')' * f_score)
	t -= 1


def max_brackets(s):
	slen = len(s)
	bal = 0
	max_bal = 0
	for x in s:
		if x == '(':
			bal += 1
		elif bal > max_bal:
			max_bal = bal
		if x == ')':
			bal -= 1
	return max_bal

def gen_brackets(max_bal):
	ans = ''
	for i in range(max_bal):
		ans += '('
	for i in range(max_bal):
		ans += ')'
	return ans
T = int(input())
for ts in range(T):
	s = input()
	max_bal = max_brackets(s)
	s1 = gen_brackets(max_bal)
	print(s1)


for _ in range(int(input())):
	s = input()
	maxb = 0
	b = 0
	for i in s:
		if i == '(':
			b += 1
		elif i == ')':
			b -= 1
		maxb = max(maxb, b)
	s = ''
	for i in range(maxb * 2):
		if i <= maxb - 1:
			s += '('
		else:
			s += ')'
	print(s)


t = int(input())
for i in range(t):
	s = input()
	bal = 0
	max_bal = 0
	b = ''
	for i in range(len(s)):
		if s[i] == '(':
			bal += 1
		else:
			bal -= 1
		max_bal = max(max_bal, bal)
	for i in range(max_bal):
		b += '('
	for i in range(max_bal):
		b += ')'
	print(b)


def funx(x):
	bal = 0
	max_bal = 0
	for i in x:
		if i == '(':
			bal += 1
		elif i == ')':
			bal -= 1
		max_bal = max(max_bal, bal)
	return max_bal
for _ in range(int(input())):
	x = funx(input())
	print('(' * x + ')' * x)


t = int(input())
for _ in range(t):
	sum = 0
	maxsum = 0
	x = str(input())
	for i in x:
		if i == '(':
			sum = sum + 1
		if i == ')':
			sum = sum - 1
		maxsum = max(maxsum, sum)
	for i in range(maxsum):
		print('(', end='')
	for i in range(maxsum):
		print(')', end='')
	print('\n')


def f(par):
	maxBalance = 0
	balance = 0
	for x in par:
		if x == '(':
			balance += 1
		else:
			balance -= 1
		maxBalance = max(maxBalance, balance)
	return maxBalance
t = int(input())
while t != 0:
	st = input()
	n = f(st)
	ans = '(' * n + ')' * n
	print(ans)
	t -= 1


T = int(input())
for _ in range(T):
	A = input()
	balance = 0
	max_balance = 0
	for i in range(len(A)):
		if A[i] == '(':
			balance += 1
		if A[i] == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	new_string = ''
	for n in range(max_balance):
		new_string += '('
	for m in range(max_balance):
		new_string += ')'
	print(new_string)


def bal_s(s):
	bal = 0
	mx = 0
	for i in range(len(s)):
		if s[i] == '(':
			bal += 1
		elif s[i] == ')':
			bal -= 1
		mx = max(mx, bal)
	return '(' * mx + ')' * mx
t = int(input())
for _ in range(t):
	br_s = input()
	print(bal_s(br_s))


T = int(input())
for i in range(T):
	S = input()
	M = 0
	C = 0
	for j in range(len(S)):
		if S[j] == '(':
			C += 1
		elif S[j] == ')':
			C -= 1
		M = max(M, C)
	print(M * '(' + M * ')')


for _ in range(int(input())):
	S = input()
	bal = 0
	maxbal = 0
	for s in S:
		if s == '(':
			bal += 1
		if s == ')':
			bal -= 1
		maxbal = max(bal, maxbal)
	S = '(' * maxbal + ')' * maxbal
	print(S)


def max_balance(s):
	balance = 0
	max_balance = 0
	for letter in s:
		if letter == '(':
			balance += 1
		elif letter == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance
for _ in range(int(input())):
	a = input()
	mb = max_balance(a)
	output = ''
	for i in range(mb):
		output += '('
	for i in range(mb):
		output += ')'
	print(output)


for s in range(int(input())):
	A = input()
	balance = 0
	max_balance = 0
	for i in range(len(A)):
		if A[i] == '(':
			balance += 1
		if A[i] == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	for i in range(max_balance):
		print('(', end='')
	for i in range(max_balance):
		print(')', end='')
	print()


def F(S):
	balance = 0
	max_balance = 0
	for i in S:
		if i == '(':
			balance += 1
		elif i == ')':
			balance -= 1
		max_balance = max(max_balance, balance)
	return max_balance
for _ in range(int(input())):
	x = input()
	maxi = F(x)
	tot = '(' * maxi
	tot += ')' * maxi
	print(tot)