A string consisting only of parentheses \verb+(+ and \verb+)+ is called a parentheses string. The balanced parentheses strings are defined recursively as follows:

An empty string is a balanced parentheses string.
If s is a balanced parentheses string, then \verb+(+s\verb+)+ is also a balanced parentheses string.
If s and t are balanced parentheses strings, then st (concatenation of s and t) is also a balanced parentheses string.

For a parentheses string, an operation on this string is defined as follows:
Choose any [substring] of this string which is balanced.
Remove this substring and concatenate the remaining parts.

Given a parentheses string S, find the minimum length of the string one can get by applying the above operation any number of times. Also find the minimum number of operations required to achieve this minimum length.

------ Input Format ------ 

- The first line of the input contains T, the number of test cases. Then the test cases follow.
- Each test case contains string S in a single line, which consists only of the characters \verb+(+ and \verb+)+.

------ Output Format ------ 

For each test case, in a single line output the minimum length of the string we can get by applying the given operation any number of times and the minimum number of operations required to achieve this minimum length separated by a single space.

------ Constraints ------ 

$1 ≤ T ≤ 10^{6}$
$1 ≤ |S| ≤ 2 \cdot 10^{6}$
- Sum of $|S|$ over all test cases does not exceed $2 \cdot 10^{6}$.

----- Sample Input 1 ------ 
3
(())
)()(
()(()

----- Sample Output 1 ------ 
0 1
2 1
1 2

----- explanation 1 ------ 
Test Case $1$: The given string is balanced and hence we can choose the whole string for the operation and remove it. So, the minimum length of the string we can achieve is equal to $0$ and it requires a minimum of $1$ operation to achieve this.

Test Case $2$: The only non-empty balanced substring of $\verb+)()(+$ is $\verb+()+$. By applying the operation once, the string changes to $\verb+)(+$. This string has no non-empty balanced substring. Therefore, the minimum length of the string we can achieve is equal to $2$ and it requires a minimum of $1$ operation to achieve this.

Test Case $3$: Apply the operation on the string $S = \verb+()(()+$ by removing the substring $S[1,2] = \verb+()+$ to get $\verb+(()+$. Now, apply the operation by removing the substring $\verb+()+$ to get $($. Therefore, the minimum length of the string we can achieve is equal to $1$ and it requires a minimum of $2$ operations to achieve this.

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	s = input()
	par = {'(': ')'}
	stack = []
	i = 0
	res = []
	while i < len(s):
		flag = 0
		if stack and stack[-1][0] != ')' and (par[stack[-1][0]] == s[i]):
			(val, index) = stack.pop()
			res += [index, i]
			flag = 1
		if not flag:
			stack.append((s[i], i))
		i += 1
	res.sort()
	diff = []
	for i in range(len(res) - 1):
		diff.append(abs(res[i] - res[i + 1]))
	if diff:
		count = 1
	else:
		count = 0
	for i in range(len(diff) - 1):
		if diff[i] == diff[i + 1] == 1:
			pass
		elif diff[i] != 1 and diff[i + 1] == 1:
			count += 1
	print(len(stack), count)


import math
T = int(input())
for _ in range(T):
	s = input()
	l = []
	N = len(s)
	for i in range(N):
		if len(l) == 0:
			l.append(i)
			continue
		if s[i] == ')':
			if s[l[-1]] == '(':
				l.pop()
			else:
				l.append(i)
		else:
			l.append(i)
	print(len(l), end=' ')
	i = 0
	s = 0
	for j in range(len(l)):
		if i == l[j]:
			i += 1
		else:
			i = l[j] + 1
			s += 1
	if i != N:
		s += 1
	print(s)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	stk = [(0, s[0])]
	ls = 1
	for i in range(1, n):
		if ls == 0:
			stk.append((i, s[i]))
			ls += 1
			continue
		(c1, c2) = (stk[-1][1], s[i])
		if c1 == '(' and c2 == ')':
			stk.pop()
			ls -= 1
		else:
			stk.append((i, c2))
			ls += 1
	ls = len(stk)
	ans2 = 0
	if ls != 0:
		for i in range(1, ls):
			if stk[i][0] - stk[i - 1][0] != 1:
				ans2 += 1
		if stk[0][0] != 0:
			ans2 += 1
		if stk[-1][0] != n - 1:
			ans2 += 1
	else:
		ans2 += 1
	print(ls, ans2)


T = int(input())
for i in range(T):
	A = str(input())
	stack = []
	top = 0
	for j in range(len(A)):
		if top and stack[top - 1][0] == '(' and (A[j] == ')'):
			stack.pop()
			top = top - 1
		else:
			stack.append((A[j], j))
			top = top + 1
	total = 0
	prev = 0
	if len(stack):
		for j in range(len(stack)):
			if not j:
				if stack[j][1]:
					total = total + 1
			elif prev < stack[j][1] - 1:
				total = total + 1
			prev = stack[j][1]
		if not stack[len(stack) - 1][1] == len(A) - 1:
			total = total + 1
		print(len(stack), total)
	else:
		print(0, 1)


for _ in range(int(input())):
	s = input()
	n = len(s)
	(st, e) = ([], [])
	for i in range(n):
		if s[i] == ')':
			if st:
				st.pop()
			else:
				e.append(i)
		else:
			st.append(i)
	r = st + e
	if r:
		r.sort()
		nr = len(r)
		c = (r[0] != 0) + (r[nr - 1] != n - 1)
		for i in range(1, nr):
			c += r[i] - r[i - 1] > 1
		print(nr, c)
	else:
		print(0, 1)


for _ in range(int(input())):
	s = input()
	n = len(s)
	track = []
	prev = []
	status = [0 for _ in range(n)]
	for i in range(n):
		if s[i] == '(':
			prev.append(i)
		elif len(prev):
			if prev[-1] == i - 1:
				track.append(2)
			else:
				track[-1] = track[-1] + 2
			status[i] = 1
			temp = prev.pop()
			if temp != 0 and status[temp - 1] == 1:
				track[-2] = track[-2] + track[-1]
				track.pop()
	print(n - sum(track), len(track))


t = int(input())
import collections

def solve():
	a = input()
	n = len(a)
	s = []
	cur = 0
	for i in range(n):
		if cur == 0:
			s.append(i)
			cur = 1
		elif a[i] == '(':
			s.append(i)
			cur += 1
		elif a[s[-1]] == '(':
			s.pop()
			cur -= 1
		else:
			s.append(i)
			cur += 1
	r = len(s)
	st = 0
	m = 0
	for i in range(r):
		if s[i] > st:
			m += 1
			st = s[i] + 1
		else:
			st = s[i] + 1
	if r == 0 or s[r - 1] < n - 1:
		m += 1
	print(r, m)
while t > 0:
	solve()
	t -= 1


def paran(S):
	st = [-1]
	ans = []
	op = 0
	for l in range(len(S)):
		if S[l] == '(':
			st.append(l)
		else:
			st.pop()
			if len(st) != 0:
				if len(ans) == 0:
					ans.append(st[-1])
				elif ans[-1] > st[-1]:
					ans.pop()
					if len(ans) > 0 and ans[-1] != st[-1]:
						ans.append(st[-1])
					if len(ans) == 0:
						ans.append(st[-1])
				elif ans[-1] < st[-1]:
					ans.append(st[-1])
			else:
				op = op + 1
				st.append(l)
	print(op - 1 + len(st), end=' ')
	print(len(ans))
for _ in range(int(input())):
	s = input()
	paran(s)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

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

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

def inpu():
	return int(inp())

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

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

def sep():
	return map(int, inp().split())

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

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		s = inp()
		n = len(s)
		stack = []
		for i in range(n):
			if s[i] == '(':
				stack.append(i)
			elif stack and s[stack[-1]] == '(':
				stack.pop()
			else:
				stack.append(i)
		(ans, prev) = (0, 0)
		for i in stack:
			if i - prev > 1:
				ans += 1
			prev = i
		if prev != len(s) - 1:
			ans += 1
		print(len(stack), ans)
main()


for _ in range(int(input())):
	s = input()
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif len(stack) != 0 and s[stack[-1]] == '(':
			stack.pop()
		else:
			stack.append(i)
	count = 0
	prev = 0
	for i in stack:
		if i - prev > 1:
			count += 1
		prev = i
	if len(s) - prev > 1:
		count += 1
	print(len(stack), count)


for _ in range(int(input())):
	s = input()
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append((s[i], i))
		elif s[i] == ')':
			if stack != [] and stack[-1][0] == '(':
				stack.pop()
			else:
				stack.append((s[i], i))
	st = -1
	ans = 0
	stack = [('0', -1)] + stack + [('0', len(s))]
	for i in range(1, len(stack)):
		if stack[i][1] - stack[i - 1][1] > 1:
			ans += 1
	print(len(stack) - 2, ans)


import sys
import os
from sys import stdin, stdout
io_path = 'E:\\Personal\\competitve-programming\\IO'
if os.path.exists(io_path):
	sys.stdout = open(io_path + '/output.txt', 'w')
	sys.stdin = open(io_path + '/input.txt', 'r')

def get_ints():
	return map(int, input().strip().split())

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

def get_string():
	return input().strip()
test_cases = int(input())
while test_cases > 0:
	s = get_string()
	v = []
	res = []
	index = 0
	while index <= len(s) - 1:
		if s[index] == '(':
			v.append(index + 1)
		else:
			v.append(-(index + 1))
		index += 1
	index = 0
	while index <= len(v) - 1:
		if v[index] > 0:
			res.append(v[index])
		elif len(res) > 0 and res[-1] > 0:
			res.pop()
		else:
			res.append(v[index])
		index += 1
	min_length = len(res)
	for i in range(len(res)):
		if res[i] < 0:
			res[i] *= -1
		res[i] -= 1
	operations = 0
	if len(res) == 0:
		operations = 1
	else:
		if res[0] > 0:
			operations += 1
		for i in range(1, len(res)):
			if res[i] - res[i - 1] > 1:
				operations += 1
		if res[-1] < len(s) - 1:
			operations += 1
	print(min_length, operations)
	test_cases -= 1


for _ in range(int(input())):
	s = input()
	n = len(s)
	l = list()
	l.append([s[0], 0])
	for i in range(1, n):
		if len(l) == 0:
			l.append([s[i], i])
			continue
		temp = l[-1][0]
		if s[i] == ')' and temp == '(':
			l.pop()
		else:
			l.append([s[i], i])
	rem = len(l)
	oper = 1
	if len(l) > 0:
		oper = 0
		temp = l[-1]
		l.pop()
		if temp[1] != n - 1:
			oper += 1
		while len(l) > 0:
			temp1 = l[-1]
			if temp1[1] + 1 != temp[1]:
				oper += 1
			l.pop()
			temp = temp1
		if temp[1] != 0:
			oper += 1
	print(rem, oper)


for _ in range(int(input())):
	s = input()
	stack = []
	rem = []
	ans = 0
	for (i, el) in enumerate(s):
		if el == '(':
			stack.append(i)
		elif stack:
			stack.pop()
		else:
			rem.append(i)
	left = len(stack) + len(rem)
	if left == len(s):
		print(left, 0)
	elif left == 0:
		print(0, 1)
	else:
		ans = 0
		a = stack + rem
		res = [-1]
		prev = res[-1]
		a.sort()
		for el in a:
			if res and prev + 1 == el:
				pass
			else:
				res.append(el)
			prev = el
		if prev + 1 != len(s):
			res.append(len(s) - 1)
		print(left, len(res) - 1)


for _ in range(int(input())):
	A = input()
	s = []
	n = len(A)
	for i in range(n):
		if A[i] == '(':
			s.append(i)
		elif s and A[s[-1]] == '(':
			s.pop()
		else:
			s.append(i)
	ops = 0
	curr = 0
	for i in range(len(s)):
		if curr == s[i]:
			curr += 1
		else:
			curr = s[i] + 1
			ops += 1
	if curr != n:
		ops += 1
	print(len(s), ops)


from collections import deque

def solve(b):
	stack = deque()
	st = []
	n = len(b)
	for (i, s) in enumerate(b):
		if s == '(':
			st.append(s)
			stack.append(i)
		elif len(st) == 0 or st[-1] != '(':
			st.append(s)
			stack.append(i)
		else:
			st.pop()
			stack.pop()
	if len(stack) == 0:
		print(0, 1)
	elif len(stack) == 1:
		top = stack.pop()
		if top == 0 or top == n - 1:
			if n > 1:
				print(1, 1)
			else:
				print(1, 0)
		else:
			print(1, 2)
	else:
		length = len(stack)
		top = stack.popleft()
		second = stack[0]
		count = 0
		if top == 0:
			if second - top > 1:
				count += 1
		elif second - top == 1:
			count += 1
		else:
			count += 2
		while len(stack) >= 2:
			top = stack.popleft()
			second = stack[0]
			if second - top > 1:
				count += 1
		top = stack.popleft()
		if top != n - 1:
			count += 1
		print(length, count)
for _ in range(int(input())):
	b = input().strip()
	solve(b)


from collections import deque
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	a = [1] * n
	st = deque()
	for (i, v) in enumerate(s):
		if v == '(':
			st.append(('(', i))
		elif len(st) > 0:
			(e, p) = st.pop()
			a[i] = a[p] = 0
	b = [a[0]]
	(count, ones) = (0, 0)
	for i in range(1, n):
		if a[i] != a[i - 1]:
			b.append(a[i])
	for i in b:
		if i == 0:
			count += 1
	for i in a:
		if i == 1:
			ones += 1
	print(ones, count)


for _ in range(int(input())):
	s = input()
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
			should_count = True
		elif len(stack) > 0 and s[stack[-1]] == '(':
			stack.pop()
		else:
			stack.append(i)
	c = 0
	prev = 0
	for idx in stack:
		if idx - prev > 1:
			c += 1
		prev = idx
	if len(s) - prev > 1:
		c += 1
	print(len(stack), c)


for _ in range(int(input())):
	s = input()
	vals = [False for i in s]
	last_open = [-1]
	for i in range(len(s)):
		if s[i] == ')' and last_open[-1] >= 0:
			vals[last_open[-1]] = True
			vals[i] = True
			temp = last_open.pop()
		elif s[i] == '(':
			last_open.append(i)
	prev = False
	final_len = len(s) - sum(vals)
	count = 0
	for i in vals:
		if i and (not prev):
			count += 1
		prev = i
	print(final_len, count, sep=' ')


t = int(input())
for _ in range(t):
	s = input()
	total = 0
	depth = 0
	starting = False
	start_index = -1
	end_index = -1
	i = 0
	while i < len(s):
		if not starting and s[i] == '(':
			start_index = i
			starting = True
			depth = 1
		elif starting:
			if s[i] == '(':
				depth += 1
			else:
				depth -= 1
				if depth == 0:
					end_index = i
				elif depth == -1:
					i -= 1
					new_s = ''
					if start_index > 0:
						new_s = s[0:start_index]
					if i < len(s) - 1:
						new_s += s[i + 1:]
					s = new_s
					i = start_index
					end_index = start_index
					starting = False
					total += 1
		i += 1
	if end_index > start_index:
		new_s = ''
		if start_index > 0:
			new_s = s[0:start_index]
		if end_index < len(s) - 1:
			new_s += s[end_index + 1:]
		s = new_s
		starting = False
		total += 1
	i = len(s) - 1
	starting = False
	while i >= 0:
		if not starting and s[i] == ')':
			start_index = i
			end_index = start_index
			starting = True
			depth = 1
		elif starting:
			if s[i] == ')':
				depth += 1
			else:
				depth -= 1
				if depth == 0:
					end_index = i
				elif depth == -1:
					i += 1
					new_s = ''
					if i > 0:
						new_s += s[0:i]
					if start_index < len(s) - 1:
						new_s += s[start_index + 1:]
					s = new_s
					starting = False
					end_index = start_index
					total += 1
		i -= 1
	if end_index < start_index:
		new_s = ''
		if end_index > 0:
			new_s += s[0:end_index]
		if start_index < len(s) - 1:
			new_s += s[start_index + 1:]
		s = new_s
		starting = False
		total += 1
	print(len(s), total)


t = int(input())
for _ in range(t):
	s = input()
	stack = []
	rest = 0
	ans = []
	for (idx, c) in enumerate(s):
		if c == ')':
			if stack:
				ans.append(idx)
				ans.append(stack[-1])
				stack.pop()
			else:
				rest += 1
		else:
			stack.append(idx)
	rest += len(stack)
	ans.sort()
	if ans:
		cnt = 1
	else:
		cnt = 0
	for i in range(1, len(ans)):
		if ans[i - 1] + 1 != ans[i]:
			cnt += 1
	print(rest, cnt)


for _ in range(int(input())):
	s = input()
	st = []
	temp = []
	arr = [0 for _ in range(len(s))]
	s = list(s)
	for (i, c) in enumerate(s):
		if c == '(':
			st.append(i)
		elif len(st):
			arr[i] += 1
			arr[st[-1]] += 1
			st.pop()
	flag = 0
	ans = 0
	count = 0
	for e in arr:
		if e == 0:
			ans += 1
			flag = 0
		elif flag == 0:
			count += 1
			flag = 1
	print(ans, count)


import sys
from math import sqrt, gcd, factorial, ceil, floor
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	s = S()
	n = len(s)
	st = []
	st2 = []
	for i in range(n):
		if s[i] == '(':
			st.append(i)
		elif st:
			st.pop()
		else:
			st2.append(i)
	st += st2
	st.sort()
	if not st:
		print(0, 1)
		continue
	ans2 = len(st)
	ans = 0
	if st and st[0] != 0:
		ans += 1
	if len(st) > 0 and st[-1] != n - 1:
		ans += 1
	while st:
		temp = st.pop()
		ans += 1
		while st and st[-1] + 1 == temp:
			temp = st.pop()
	print(ans2, ans - 1)