You are given a bracket sequence consisting of $n$ characters '(' and/or )'. You perform several operations with it.

During one operation, you choose the shortest prefix of this string (some amount of first characters of the string) that is good and remove it from the string.

The prefix is considered good if one of the following two conditions is satisfied:

this prefix is a regular bracket sequence;

this prefix is a palindrome of length at least two.

A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not.

The bracket sequence is called palindrome if it reads the same back and forth. For example, the bracket sequences )), (( and )(() are palindromes, while bracket sequences (), )( and ))( are not palindromes.

You stop performing the operations when it's not possible to find a good prefix. Your task is to find the number of operations you will perform on the given string and the number of remaining characters in the string.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The next $2t$ lines describe test cases.

The first line of the test case contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the length of the bracket sequence.

The second line of the test case contains $n$ characters '(' and/or ')' — the bracket sequence itself.

It is guaranteed that the sum of $n$ over all test cases do not exceed $5 \cdot 10^5$ ($\sum n \le 5 \cdot 10^5$).


-----Output-----

For each test case, print two integers $c$ and $r$ — the number of operations you will perform on the given bracket sequence and the number of characters that remain in the string after performing all operations.


-----Examples-----

Input
5
2
()
3
())
4
((((
5
)((()
6
)((()(
Output
1 0
1 1
2 0
1 0
1 1


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

def solve(n, s):
	idx = 0
	ops = 0
	while idx < n:
		if idx == n - 1:
			print(ops, 1)
			return
		if s[idx] == '(':
			idx += 2
			ops += 1
		elif s[idx + 1] == ')':
			ops += 1
			idx += 2
		else:
			idx2 = idx + 1
			while idx2 < n and s[idx2] == '(':
				idx2 += 1
			if idx2 == n:
				print(ops, n - idx)
				return
			else:
				ops += 1
				idx = idx2 + 1
	print(ops, n - idx)
	return
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	solve(n, s)


for s in [*open(0)][2::2]:
	n = len(s)
	s += ')'
	i = c = 0
	while i < n:
		c += 1
		j = i
		if ')' > s[i]:
			i += 2
		else:
			i = s.find(')', i + 1) + 1
	print(c - 1, n - j - 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	i = 0
	while True:
		if i >= n - 1:
			print(c, max(n - i, 0))
			break
		if s[i] == '(':
			i += 2
			c += 1
		else:
			try:
				i = s.index(')', i + 1) + 1
				c += 1
			except:
				print(c, n - i)
				break


import math

def nado(n, s):
	(i, j) = (0, 1)
	ans = 0
	while i < n and j < n:
		if s[i] == '(':
			ans += 1
			i += 2
			j = i + 1
		else:
			while j < n and s[j] != ')':
				j += 1
			if j >= n:
				break
			ans += 1
			i = j + 1
			j = i + 1
	if i == n:
		return [ans, 0]
	return [ans, n - i]
for t in range(int(input())):
	n = int(input())
	s = input()
	print(*nado(n, s))


def solve():
	n = int(input())
	seq = input()
	solved = 0
	ops = 0
	prev = None
	tmp = 0
	for c in seq:
		if prev == None:
			prev = c
		elif prev == '(':
			solved += 2
			prev = None
			ops += 1
		elif c == '(':
			tmp += 1
		else:
			solved += 2 + tmp
			tmp = 0
			prev = None
			ops += 1
	print(ops, n - solved)
for tc in range(int(input())):
	solve()


def solve():
	n = int(input())
	s = input()
	if n == 1:
		print(0, 1)
		return
	steps = 0
	done = -1
	i = 0
	while i < n:
		if i == n - 1:
			break
		if s[i] == '(':
			steps += 1
			i += 2
			done = i - 1
		else:
			i += 1
			while i < n and s[i] == '(':
				i += 1
			if i == n:
				break
			steps += 1
			done = i
			i += 1
	print(steps, n - done - 1)
for _ in range(int(input())):
	solve()


from sys import stdin
input = stdin.readline
for test in range(int(input())):
	n = int(input())
	s = input()
	(c, i) = (0, 0)
	while i + 1 < n:
		if s[i] == '(':
			i += 2
			c += 1
		else:
			j = i + 1
			while j < n and s[j] != ')':
				j += 1
			if j < n:
				c += 1
				i = j + 1
			else:
				break
	print(c, n - i)


import math
import sys
import statistics
from statistics import mode
input = sys.stdin.readline

def inp_int():
	return int(input())

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

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

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

def lst_to_str(lst):
	return ' '.join((str(e) for e in lst))

def is_square(i: int) -> bool:
	return i == int(math.sqrt(i)) ** 2

def solve():
	n = inp_int()
	my_str = inp_string()
	ops = 0
	state = 0
	valid = True
	first = True
	last_idx = -1
	for (i, c) in enumerate(my_str):
		if first:
			first = False
			token = c
		elif c == token:
			ops += 1
			valid = True
			first = True
			state = 0
			last_idx = i
			continue
		state = state + 1 if c == '(' else state - 1
		if state < 0:
			valid = False
		if valid and state == 0:
			ops += 1
			valid = True
			first = True
			state = 0
			last_idx = i
			continue
	print(ops, n - last_idx - 1)
number_cases = inp_int()
for x in range(number_cases):
	solve()


def main():
	length = int(input())
	lst = []
	for _ in range(length):
		n = int(input())
		(res, left) = solver(input())
		lst.append((res, left))
	for (res, left) in lst:
		print(str(res) + ' ' + str(left))

def solver(string):
	base = ''
	res = 0
	left = 0
	n = len(string)
	for i in range(n):
		if base == '':
			base = string[i]
			left = 1
		elif base == '(':
			base = ''
			left = 0
			res += 1
		elif string[i] == ')':
			left = 0
			res += 1
			base = ''
		else:
			left += 1
	return (res, left)
main()


def fun(n, s):
	op = 0
	i = 0
	while i < n:
		if i == n - 1:
			return (op, 1)
		if s[i] == '(':
			op += 1
			i += 2
		else:
			temp = i + 1
			while temp < n and s[temp] != ')':
				temp += 1
			if temp >= n:
				return (op, n - i)
			i = temp + 1
			op += 1
	return (op, 0)
for _ in range(int(input())):
	n = int(input())
	s = input()
	result = fun(n, s)
	print(result[0], result[1])


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlist():
	return input().split(' ')

def yes(t):
	if t:
		return 'YES'
	return 'NO'

def printjoin(l, str=False):
	if str:
		l = [str(i) for i in l]
	return ' '.join(l)

def power_of_two(n):
	b = bin(n)[2:]
	return int(b) == 10 ** (len(b) - 1)

def bit_count(n):
	return bin(n).count('1')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	lcm = x * y // gcd(x, y)
	return lcm

def isint(str):
	try:
		int(str)
		return True
	except ValueError:
		return False

def solve():
	n = int(input())
	ml = n
	s = input()
	ans = n * [0]
	nn = -1
	for i in range(n - 1, -1, -1):
		if s[i] == ')':
			ans[i] = nn
			nn = i
	op = i = 0
	while i < ml - 1:
		if ans[i] == 0:
			i += 2
			op += 1
			n -= 2
		elif ans[i] == -1:
			break
		else:
			op += 1
			n = n - ans[i] - 1
			i = ans[i] + 1
	return '{} {}'.format(op, ml - i)
t = input()
for tt in range(int(t)):
	print(solve())


def solve():
	n = int(input())
	s = input()
	i = 0
	ans = 0
	while i < n - 1:
		if s[i] == '(':
			ans += 1
			i += 2
		else:
			j = i + 1
			while j < n and s[j] == '(':
				j += 1
			if j == n:
				break
			i = j + 1
			ans += 1
	print(ans, n - i)
tst = int(input())
for i in range(tst):
	solve()


def solve(t):
	n = int(input())
	s = input().strip()
	cnt = 0
	i = 0
	while i + 2 <= n:
		if s[i] == '(':
			cnt += 1
			i += 2
		else:
			j = i
			i += 1
			while i < n and s[i] == '(':
				i += 1
			if i == n:
				i = j
				break
			i += 1
			cnt += 1
	print(cnt, n - i)
for t in range(int(input())):
	solve(t)


n = int(input())
for _ in range(n):
	n = int(input())
	s = input()
	ans = 0
	index = 0
	while index + 1 < n:
		if s[index] == '(':
			index += 2
			ans += 1
		else:
			index_r = s.find(')', index + 1)
			if index_r == -1:
				break
			else:
				index = index_r + 1
				ans += 1
	print(ans, n - index)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
import heapq
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 998244353

def func():
	n = inp()
	s = strng()
	l = 0
	cnt = 0
	while l < n - 1:
		if s[l] == '(':
			l += 2
		elif s[l + 1] == ')':
			l += 2
		else:
			r = l + 1
			while r < n and s[r] != ')':
				r += 1
			if r == n:
				break
			l = r + 1
		cnt += 1
	return [cnt, n - l]
t = inp()
for i in range(t):
	print(*func())


def pharaoh():
	n = int(input())
	s = input()
	l = 0
	cnt = 0
	while l + 1 < n:
		if s[l] == '(' or (s[l] == ')' and s[l + 1] == ')'):
			l += 2
		else:
			r = l + 1
			while r < n and s[r] != ')':
				r += 1
			if r == n:
				break
			l = r + 1
		cnt += 1
	print(cnt, n - l)
for i in range(int(input())):
	pharaoh()


def main():
	for _ in range(int(input())):
		(n, s) = (int(input()), input())
		(l, c) = (0, 0)
		while l + 1 < n:
			if s[l] == '(' or (s[l] == ')' and s[l + 1] == ')'):
				l += 2
			else:
				r = l + 1
				while r < n and s[r] != ')':
					r += 1
				if r == n:
					break
				l = r + 1
			c += 1
		print(str(c) + ' ' + str(n - l))
main()


import sys
getline = sys.stdin.readline

def read_int():
	return int(getline())

def read_ints():
	return list(map(int, getline().split()))

def read_s():
	return str(getline().strip())

def read_ss():
	return list(map(str, getline().strip().split()))
result = []
t = read_int()
for _ in range(t):
	n = read_int()
	s = read_s()
	good = 0
	(l, r) = (0, 1)
	while r < n:
		if s[l] == ')':
			if s[r] == '(':
				r += 1
			else:
				good += 1
				l = r + 1
				r = l + 1
		else:
			good += 1
			l = r + 1
			r = l + 1
	rem = n - l
	result.append((good, rem))
for r in result:
	print(*r)


def main():
	n = int(input())
	s = list(input())
	curr = 0
	c = 0
	i = 0
	while n - i > 1:
		if s[i] == s[i + 1]:
			i += 2
			c += 1
		else:
			break
	while n - i > 1:
		if s[i] == '(' and s[i + 1] == ')':
			i += 2
			c += 1
		elif s[i] == s[i + 1]:
			i += 2
			c += 1
		else:
			if n - i < 3:
				break
			flag = True
			for j in range(i + 2, n):
				if s[j] == ')':
					c += 1
					i = j + 1
					flag = False
					break
			if flag:
				break
	print(c, n - i)
	return
for _ in range(int(input())):
	main()


import collections
import math

def main():
	n = int(input())
	s = str(input())
	balance = 0
	ans = 0
	last = 0
	i = 0
	while i < n:
		if balance == 1:
			if s[i] == ')':
				ans += 1
				balance = 0
				last = i + 1
		elif s[i] == '(' and i + 1 < n:
			ans += 1
			i += 1
			last = i + 1
		else:
			balance = 1
		i += 1
	print(ans, n - last)
t = int(input())
while t > 0:
	main()
	t -= 1


import sys
import math
T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	(l, cnt) = (0, 0)
	while l + 1 < n:
		if s[l] == '(' or (s[l] == ')' and s[l + 1] == ')'):
			l += 2
		else:
			r = l + 1
			while r < n and s[r] != ')':
				r += 1
			if r == n:
				break
			l = r + 1
		cnt += 1
	print('{} {}'.format(cnt, n - l))


t = int(input())
while t:
	n = int(input())
	s = input()
	cur = 0
	op = 0
	while True:
		if cur >= n - 1:
			print(op, max(n - cur, 0))
			break
		if s[cur] == '(':
			op += 1
			cur += 2
		else:
			try:
				cur = s.index(')', cur + 1) + 1
				op += 1
			except:
				print(op, n - cur)
				break
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	i = 0
	while i + 1 < n:
		if s[i] == '(' or (s[i] == ')' and s[i + 1] == ')'):
			i = i + 2
		else:
			r = i + 1
			while r < n and s[r] != ')':
				r += 1
			if r == n:
				break
			i = r + 1
		count += 1
	print(count, n - i)


t = int(input())

def find_answer(s):
	i = 0
	j = 0
	ops = 0
	while i < len(s):
		if s[i] == '(':
			if i < len(s) - 1:
				i += 2
				j += 2
				ops += 1
			else:
				i += 2
		else:
			i += 1
			while i < len(s) and s[i] != ')':
				i += 1
			if i < len(s):
				i += 1
				j = i
				ops += 1
	return '%s %s' % (ops, len(s) - j)
for i in range(t):
	n = int(input())
	s = input()
	print(find_answer(s))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	i = 0
	palion = 0
	lasti = 0
	while i < n:
		if s[i] == ')':
			if palion == 1:
				c += 1
				lasti = i + 1
				i += 1
				palion = 0
			elif i + 1 < n and s[i + 1] == ')':
				c += 1
				lasti = i + 2
				i += 2
			else:
				palion = 1
				i += 1
		elif palion == 1:
			i += 1
		elif i + 1 < n:
			c += 1
			i += 2
			lasti = i
		else:
			i += 1
	print(c, n - lasti)


import sys

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

def solve(N, S):
	(l, r) = (0, 0)
	(l_cnt, r_cnt) = (0, 0)
	for i in range(N):
		if S[i] == '(':
			if l_cnt:
				if r_cnt == 0:
					l_cnt -= 1
					l += 1
				else:
					l_cnt += 1
			else:
				l_cnt += 1
		elif r_cnt:
			l_cnt = 0
			r_cnt = 0
			l += 1
		elif l_cnt == 1:
			l_cnt = 0
			r_cnt = 0
			l += 1
		else:
			r_cnt += 1
	return (l, l_cnt + r_cnt)
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	(l, r) = solve(N, S)
	print(l, r)


from queue import Queue

def main():
	t = int(input())
	for tt in range(t):
		n = int(input())
		scopes = input()
		count = 0
		i = 0
		ans = False
		while i + 1 < n and (not ans):
			if scopes[i] + scopes[i + 1] in {'((', '))', '()'}:
				i += 2
				count += 1
			else:
				j = i + 1
				while j < n:
					if scopes[j] == '(':
						j += 1
					else:
						break
				if j == n:
					print(count, n - i)
					ans = True
					break
				count += 1
				if j + 1 < n:
					i = j + 1
				else:
					print(count, 0)
					ans = True
					break
		if not ans:
			print(count, n - i)
main()


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	ans = 0
	i = 0
	flag = 0
	while i < n:
		if s[i] == '(':
			if i == n - 1:
				flag = 1
				break
			i += 2
		else:
			if i == n - 1:
				flag = 1
				break
			j = i + 1
			while j < n and s[j] != ')':
				j += 1
			if j == n:
				flag = n - i
				break
			i = j + 1
		ans += 1
	print(ans, flag)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	rem = n
	ops = 0
	while i < n:
		if s[i] == '(':
			i += 1
			if i < n:
				ops += 1
				i += 1
				rem -= 2
		else:
			j = i
			i += 1
			while i < n and s[i] != ')':
				i += 1
			if i < n:
				rem -= i - j + 1
				i += 1
				ops += 1
	print(ops, rem)


t = int(input())
for i in range(t):
	n = int(input())
	z = input()
	x = ''
	b = n
	o = 0
	for i in range(n):
		if x == '':
			x = z[i]
		elif x == '(':
			b -= 2
			x = ''
			o += 1
		elif z[i] == x:
			b = n - (i + 1)
			o += 1
			x = ''
	print(o, b)


for t in range(int(input())):
	n = int(input())
	l = input()
	c = 0
	i = 0
	while i + 1 < len(l):
		if l[i] == '(' or (l[i] == ')' and l[i + 1] == ')'):
			i += 2
		else:
			r = i + 1
			while r < n and l[r] != ')':
				r += 1
			if r == n:
				break
			i = r + 1
		c += 1
	print(c, len(l) - i)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	l = 0
	ans = 0
	while l + 1 < n:
		if s[l] == '(' or (s[l] == ')' and s[l + 1] == ')'):
			l += 2
		else:
			k = l + 1
			while k < n and s[k] != ')':
				k += 1
			if k == n:
				break
			l = k + 1
		ans += 1
	print(ans, n - l)


tc = int(input())
for _ in range(tc):
	n = int(input())
	s = input()
	i = 0
	x = 0
	while i < n:
		if s[i] == '(' and n - i > 1:
			i += 2
			x += 1
		elif s[i] == ')':
			temp = i + 1
			while temp < n and s[temp] != ')':
				temp += 1
			if temp < n and s[temp] == ')':
				i = temp + 1
				x += 1
			else:
				break
		else:
			break
	print(x, n - i)


t = int(input())
for z in range(0, t):
	n = int(input())
	s1 = input()
	if n == 1:
		print(0, 1)
		continue
	pp = 0
	lit = -1
	i = 0
	while i < n:
		if i == n - 1:
			break
		if s1[i] == '(':
			pp += 1
			i += 2
			lit = i - 1
		else:
			i += 1
			while i < n and s1[i] == '(':
				i += 1
			if i == n:
				break
			pp += 1
			lit = i
			i += 1
	print(pp, n - lit - 1)


for q in range(int(input())):
	n = int(input())
	s = input()
	j = 0
	i = 0
	res = 0
	while i < n:
		if s[i] == '(':
			if i < n - 1:
				i += 2
				j = i
				res += 1
			else:
				i += 1
		else:
			i += 1
			while i < n and s[i] != ')':
				i += 1
			if i < n:
				res += 1
				i += 1
				j = i
	print(res, n - j)


for _ in range(int(input())):
	a = int(input())
	b = input()
	operations = 0
	i = 0
	bl = True
	while i < a - 1:
		if b[i] == '(' or (b[i] == ')' and b[i + 1] == ')'):
			operations += 1
			i += 2
		else:
			temp = i
			i += 1
			while b[i] == '(' and i < a - 1:
				i += 1
			if b[i] == ')':
				operations += 1
				i += 1
			else:
				bl = False
	if not bl:
		print(operations, a - temp)
	else:
		print(operations, a - i)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	op = 0
	while i < n:
		if n - i <= 1:
			break
		elif s[i:i + 2] in ['((', '))', '()']:
			i += 2
			op += 1
		else:
			for j in range(i + 1, n):
				if s[j] == ')':
					i = j + 1
					op += 1
					break
			else:
				break
	print(op, n - i)


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	j = 0
	prev = 0
	count = 0
	while j < N - 1:
		if S[j] == '(':
			count = count + 1
			j = j + 2
			prev = j
		else:
			k = j + 1
			while k < N:
				if S[k] == ')':
					count = count + 1
					j = k + 1
					prev = j
					break
				k = k + 1
				j = k
	print(count, N - prev)


for k in range(int(input())):
	n = int(input())
	s = input()
	op = 0
	i = 0
	j = 1
	while j < n:
		temp = ''
		temp += s[i]
		temp += s[j]
		if temp == '()' or temp == '))' or temp == '((':
			op += 1
			i += 2
			j += 2
		else:
			while j < n and s[j] != ')':
				j += 1
			if j < n:
				op += 1
				i = j + 1
				j = i + 1
	if n == 1:
		print(0, 1)
	elif i >= n:
		print(op, 0)
	else:
		print(op, n - i)


import math
n = int(input())
for i in range(n):
	x = int(input())
	s = input()
	something = 1
	k = 0
	op = 0
	flag = 1
	while something:
		if k >= x:
			something = 0
		elif s[k] == '(':
			if k + 1 == len(s):
				flag = 0
				c = len(s) - 1
				break
			k += 2
			op += 1
		else:
			flag = 0
			c = k
			k += 1
			while k < x:
				if s[k] == ')':
					flag = 1
					op += 1
					k += 1
					break
				k += 1
	print(op, end=' ')
	if flag:
		print(len(s) - k)
	else:
		print(len(s) - c)


for T in range(int(input())):
	n = int(input())
	s = input()
	p1 = 0
	c = 0
	while p1 + 1 < n:
		if s[p1] == '(' or (s[p1] == ')' and s[p1 + 1] == ')'):
			p1 += 2
		else:
			p2 = p1 + 1
			while p2 < n and s[p2] != ')':
				p2 += 1
			if p2 == n:
				break
			p1 = p2 + 1
		c += 1
	print(c, n - p1)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	count = 0
	i = 0
	while i + 1 < n:
		if s[i] == '(':
			i += 2
			count += 1
		else:
			j = i + 1
			while j < n and s[j] != ')':
				j += 1
			if j < n:
				count += 1
				i = j + 1
			else:
				break
	print(count, n - i)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	r = 0
	if n == 1:
		print(0, 1)
		continue
	b = 0
	for i in range(0, n):
		if i == b:
			f = s[i]
			continue
		if f == ')':
			if s[i] == f:
				c += 1
				b = i + 1
		else:
			c += 1
			b = i + 1
	print(c, n - b)


for t in range(int(input())):
	n = int(input())
	s = input()
	l = 0
	count = 0
	while l + 1 < n:
		if s[l] == '(' or (s[l] == ')' and s[l + 1] == ')'):
			l += 2
		else:
			r = l + 1
			while r < n and s[r] != ')':
				r += 1
			if r == n:
				break
			l = r + 1
		count += 1
	print(count, n - l)


def read_input():
	n = int(input())
	for _ in range(n):
		input()
		seq = input()
		print(check_brackets(seq))

def test():
	assert is_palindrome('))')
	assert is_palindrome('((')
	assert is_palindrome(')(()')
	assert not is_palindrome('()')
	assert not is_palindrome(')(')
	assert not is_palindrome('))(')
	assert is_regular('(())()')
	assert is_regular('()')
	assert is_regular('(()(()))')
	assert not is_regular(')(')
	assert not is_regular('(()')
	assert not is_regular('(()))(')

def is_palindrome(seq):
	return seq == seq[::-1]

def is_regular(seq):
	depth = 0
	for c in seq:
		if c == '(':
			depth += 1
		elif depth <= 0:
			return False
		else:
			depth -= 1
	return depth == 0

def check_brackets(seq):
	moves = 0
	start = 0
	current = 2
	seq_len = len(seq)
	while current <= seq_len:
		if current - start == 2 and seq[start:current] != ')(':
			moves += 1
			start = current
			current += 2
		elif seq[start] == seq[current - 1] and is_palindrome(seq[start:current]):
			moves += 1
			start = current
			current += 2
		else:
			current += 1
	return f'{moves} {seq_len - start}'
test()
read_input()


from math import sqrt

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

def intRd():
	return int(input())

def lstStrRd():
	return list(input())
for _ in range(intRd()):
	n = int(input())
	s = input()
	cnt = 0
	l = 0
	while l + 1 < n:
		if s[l] == '(' or (s[l] == ')' and s[l + 1] == ')'):
			l += 2
		else:
			r = l + 1
			while r < n and s[r] != ')':
				r += 1
			if r == n:
				break
			l = r + 1
		cnt += 1
	print(cnt, n - l)


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	n = I()
	s = S()
	if n == 1:
		print(0, 1)
		continue
	i = 0
	cnt = 0
	turn = 0
	while i < len(s):
		if s[i] == '(' and i + 1 < n:
			cnt += 2
			turn += 1
			i += 2
		elif s[i] == ')':
			t = i
			i += 1
			while i < n and s[i] != ')':
				i += 1
			if i == n:
				break
			turn += 1
			i += 1
			cnt += i - t
		else:
			i += 1
	print(turn, n - cnt)


from collections import defaultdict, deque
import math
t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	if n == 1:
		print(0, 1)
		continue
	c = 0
	i = 0
	x = 0
	while i < n:
		if s[i] == '(' and i != n - 1:
			c += 1
			i += 2
			x += 2
		else:
			if i == n - 1:
				break
			i += 1
			while i < n:
				if s[i] == ')':
					c += 1
					x = i
					x += 1
					break
				i += 1
			i += 1
	if x > n - 1:
		print(c, 0)
	else:
		print(c, n - x)


t = int(input())
while t:
	n = int(input())
	expr = input()
	i = 0
	op = 0
	r = 0
	while i < n:
		if expr[i] == '(':
			if i == n - 1:
				r += 1
				i += 1
			else:
				op += 1
				i += 2
		else:
			f = 0
			j = i + 1
			while j < n:
				if expr[j] == ')':
					f = 1
					op += 1
					i = j + 1
					break
				j += 1
			if f == 0:
				r = n - i
				break
	print(op, r)
	t -= 1


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	c = 0
	r = 0
	i = 0
	p = -1
	while i < n:
		if i + 1 == n:
			break
		if s[i] == '(':
			c += 1
			i = i + 2
			p = i - 1
		elif s[i] == ')':
			if s[i + 1] == ')':
				c += 1
				i = i + 2
				p = i - 1
			else:
				p = i - 1
				i = i + 1
				while i < n and s[i] != ')':
					i += 1
				if i == n:
					break
				p = i
				i += 1
				c += 1
		else:
			break
	print(c, n - p - 1)


import math
t = int(input())
while t > 0:
	n = int(input())
	s = input()
	i = 0
	st = 0
	op = 0
	while i < n - 1:
		if s[i] == '(' and s[i + 1] == '(':
			op += 1
			i += 2
			st = i
		elif s[i] == '(' and s[i + 1] == ')':
			op += 1
			i += 2
			st = i
		elif s[i] == ')' and s[i + 1] == ')':
			op += 1
			i += 2
			st = i
		else:
			i += 2
			while i < n and s[i] == '(':
				i += 1
			if i < n:
				op += 1
				st = i + 1
				i += 1
	print(op, n - st)
	t -= 1


T = int(input())
while T:
	T -= 1
	N = int(input())
	s = input()
	op = 0
	i = 0
	while i < len(s) - 1:
		if s[i] == s[i + 1]:
			op += 1
			i += 2
			continue
		if s[i] == '(' and s[i + 1] == ')':
			op += 1
			i += 2
			continue
		idx = None
		for j in range(i + 1, N):
			if s[j] == ')':
				op += 1
				idx = j
				break
		if idx is None:
			break
		i = idx + 1
	print(op, N - i) if i < N else print(op, 0)


t = int(input())
for i in range(t):
	n = int(input())
	seq = input()
	p = 0
	op = 0
	lastGoodI = 0
	while p < n:
		fc = seq[p]
		if fc == '(' and p + 1 < n:
			op += 1
			p += 2
			continue
		i = p + 1
		while i < n and seq[i] == '(':
			i += 1
		if i < n and seq[i] == ')':
			p = i + 1
			op += 1
		else:
			break
	print(op, n - p)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	t = n
	cnt = 0
	while 1:
		if i >= n - 1:
			break
		if s[i] == '(':
			cnt += 1
			i += 2
			t -= 2
		elif s[i + 1] == ')':
			cnt += 1
			i += 2
			t -= 2
		else:
			j = i + 1
			while j < n and s[j] == '(':
				j += 1
			if j == n:
				break
			elif s[j] == ')':
				cnt += 1
				t -= j + 1 - i
				i = j + 1
	print(cnt, t)


def countpalindromes(ss):
	s = '$#' + '#'.join(ss) + '#'
	n = len(s)
	p = [0] * n
	l = 0
	r = -1
	for i in range(n):
		k = 1 if i > r else min(p[l + r - i], r - i + 1)
		while i + k < n and i - k >= 0 and (s[i + k] == s[i - k]):
			k += 1
		p[i] = k
		if i + k - 1 > r:
			l = i - k + 1
			r = i + k - 1
	return [x // 2 for x in p][2::2]
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = 0
	op_amount = 0
	while True:
		if l >= len(s) - 1:
			print(op_amount, len(s) - l)
			break
		if s[l] == '(' and s[l + 1] == ')':
			l += 2
			op_amount += 1
			continue
		if s[l] == '(' and s[l + 1] == '(':
			l += 2
			op_amount += 1
			continue
		if s[l] == ')' and s[l + 1] == ')':
			l += 2
			op_amount += 1
			continue
		x = l + 2
		if x == len(s):
			print(op_amount, len(s) - l)
			break
		ended = False
		while s[x] == '(':
			x += 1
			if x == len(s):
				print(op_amount, len(s) - l)
				ended = True
				break
		if ended:
			break
		l = x + 1
		op_amount += 1


from math import *
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	ans = 0
	ele = n
	i = 0
	while i < n - 1:
		if s[i] == ')' and s[i + 1] == '(':
			j = i + 1
			while j < n:
				if s[j] == ')':
					ans += 1
					ele -= j - i + 1
					break
				j += 1
			i = j + 1
		else:
			i += 2
			ans += 1
			ele -= 2
	print(ans, ele)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	i = 0
	ret = 0
	while i < n - 1:
		if s[i] == s[i + 1]:
			ret += 1
			i += 2
			continue
		if s[i] == '(' and s[i + 1] == ')':
			ret += 1
			i += 2
			continue
		idx = -1
		for k in range(i + 1, n):
			if s[k] == ')':
				ret += 1
				idx = k
				break
		if idx == -1:
			break
		i = idx + 1
	r = 0
	if i < n:
		r = n - i
	print(f'{ret} {r}')


def ispalin(s):
	if len(s) == 1:
		return False
	if s == s[::-1]:
		return True
	return False

def isregular(exp):
	flag = True
	count = 0
	for i in range(len(exp)):
		if exp[i] == '(':
			count += 1
		else:
			count -= 1
		if count < 0:
			flag = False
			break
	if count != 0:
		flag = False
	return flag
for _ in range(int(input())):
	n = int(input())
	s = input()
	cs = s[0]
	ans = 0
	r = len(s)
	f = 0
	sf = 0
	i = 0
	while i < n:
		if i == n - 1:
			break
		if cs == '(':
			ans += 1
			r = r - 2
			i = i + 2
			if i >= n:
				break
			cs = s[i]
		elif cs == ')':
			j = i
			i = i + 1
			while i < n and s[i] != ')':
				i = i + 1
			if i == n:
				break
			ans += 1
			r = r - (i - j + 1)
			i = i + 1
			if i < n:
				cs = s[i]
			else:
				break
		else:
			i = i + 1
	print(ans, r)


import math
for k in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	c = 0
	p = -1
	d = -1
	r = 0
	l = 0
	while i < n - 1:
		if s[i] == '(' and (s[i + 1] == '(' or s[i + 1] == ')'):
			i += 2
			c += 1
			continue
		elif s[i] == ')' and s[i + 1] == ')':
			i += 2
			c += 1
			continue
		else:
			a = i + 1
			m = -1
			for z in range(a, n):
				if s[z] == ')':
					c += 1
					i = z + 1
					m = 0
					break
			if m == -1:
				p = 1
				break
	if i < n:
		print(c, n - i)
	else:
		print(c, 0)


test = int(input())
for i in range(test):
	n = int(input())
	s = input()
	c = 0
	r = 0
	i = 0
	while i < n:
		if i == n - 1 and s[i] == '(':
			r += 1
			break
		if s[i] == '(':
			c += 1
			i += 2
			continue
		if s[i] == ')' and i == n - 1:
			r += 1
			break
		if s[i] == ')':
			i += 1
			r += 1
			while i < n:
				if s[i] == ')':
					c += 1
					r = 0
					i += 1
					break
				else:
					i += 1
					r += 1
	print(c, r)


a = int(input())
for x in range(a):
	b = int(input())
	c = input()
	if b == 1:
		print(0, 1)
	elif b == 2:
		if c == '()':
			print(1, 0)
		elif c == '((' or c == '))':
			print(1, 0)
		else:
			print(0, 2)
	else:
		n = 0
		s = 0
		while n < b:
			if c[n] == '(' and n <= b - 2:
				n += 2
				s += 1
			elif c[n] == ')':
				p = n + 1
				h = 0
				while True:
					if p > b - 1:
						h = -1
						break
					elif c[p] == ')':
						break
					else:
						p += 1
				if h == -1:
					break
				else:
					n = p + 1
					s += 1
			else:
				break
		print(s, b - n)


import sys
input = sys.stdin.readline
for _ in [0] * int(input()):
	n = int(input())
	s = input()
	i = op = 0
	j = 1
	while j < n:
		if s[i] == s[j] or (s[i] + s[j] == '()' and j == i + 1):
			op = op + 1
			i = j + 1
			j = i + 1
		else:
			j = j + 1
	print(op, n - i)


import sys
from collections import Counter
n = int(input())
for t in range(n):
	len_s = int(input())
	s = input().strip()
	len_s = len(s)
	opers = 0
	position = 0
	while True:
		if len_s - position <= 1:
			break
		if s[position:position + 2] in ('((', '))', '()'):
			opers += 1
			position += 2
		else:
			first_closed = -1
			for i in range(position + 1, len(s)):
				if s[i] == ')':
					first_closed = i
					break
			if first_closed != -1:
				opers += 1
				position = first_closed + 1
			else:
				break
	print(opers, len(s) - position)


for q in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	i = 0
	while i < n:
		if s[i] == '(' and i < n - 1:
			count += 1
			i += 2
		elif s[i] == ')':
			flag = 0
			for j in range(i + 1, n):
				if s[j] == ')':
					flag = 1
					i = j + 1
					break
			if flag:
				count += 1
			else:
				break
		else:
			break
	print(count, n - i)


t = int(input())
for _ in range(t):
	n = int(input())
	test_case = input()
	i = 0
	c = 0
	r = 0
	while i < n:
		if test_case[i] == '(':
			if i == n - 1:
				i += 1
				r += 1
			else:
				c += 1
				i += 2
		else:
			f = 0
			for j in range(i + 1, n):
				if test_case[j] == ')':
					c += 1
					f += 1
					i = j + 1
					break
			if f == 0:
				r = n - i
				break
	print(c, r)


t = int(input())
for _ in range(t):
	n = int(input())
	br = input()
	i = 0
	j = 1
	ans = 0
	res = 0
	while i < len(br):
		if br[i] == ')':
			j = i + 1
			while j < len(br) and br[j] != ')':
				j += 1
			if j == len(br):
				res = len(br) - i
				break
			else:
				ans += 1
				i = j + 1
		else:
			if i < len(br) - 1:
				ans += 1
			else:
				res = 1
				break
			i = i + 2
	print(ans, res)


def findCR(exp):
	(c, r) = (0, len(exp))
	stack = []
	start = 0
	for (i, char) in enumerate(exp):
		if i == start:
			stack.append(0) if char == '(' else stack.append(1)
			continue
		elif exp[start] == char:
			c += 1
			r -= i - start + 1
			start = i + 1
			while stack:
				stack.pop()
			continue
		elif char == ')' and stack[-1] == 0:
			stack.pop()
		else:
			stack.append(0) if char == '(' else stack.append(1)
		if not stack:
			c += 1
			r -= i - start + 1
			start = i + 1
	print(c, r)
t = int(input())
while t > 0:
	l = int(input())
	seq = input()
	findCR(seq)
	t -= 1


from tabnanny import check
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = 0
	i = 0
	while i < n - 1:
		temp = s[i:i + 2]
		if temp == '()' or temp == '((' or temp == '))':
			i += 2
			c += 1
		else:
			j = i
			i += 2
			while i < n and s[i] != ')':
				i += 1
			if i == n:
				i = j
				break
			else:
				i += 1
				c += 1
	print(c, n - i)


case = int(input())
for i in range(case):
	count = int(input())
	bracs = input()
	num_o_op = 0
	current_i = 0
	opts = 0
	while current_i < count:
		first_two = ''
		if current_i + 1 < count:
			first_two = bracs[current_i:current_i + 2]
		if first_two == '()' or first_two == '((' or first_two == '))':
			num_o_op += 1
			current_i += 2
			opts += 2
		else:
			inc_flag = True
			while current_i + 1 < count:
				if bracs[current_i + 1] == ')':
					num_o_op += 1
					current_i += 2
					opts = current_i
					inc_flag = False
					break
				else:
					current_i += 1
			if inc_flag:
				current_i += 1
	print(str(num_o_op) + ' ' + str(count - opts))


from itertools import count
p = lambda a: print(a)
iip = lambda : int(input())
sip = lambda : input()
mip = lambda : map(int, input().strip().split())
lip = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
flr = lambda x: int(x)
tstcs = lambda : range(int(input()))
for t in tstcs():
	n = iip()
	s = sip()
	if n == 1:
		print('0 1')
	else:
		c = 0
		op = 0
		i = 0
		while i < n:
			if s[i] == '(' and i != n - 1:
				op += 1
				c = 0
				i += 1
			elif s[i] == '(' and i == n - 1:
				c = 1
				i += 1
			else:
				c += 1
				while i + 1 < n and s[i + 1] != ')':
					i += 1
					c += 1
				if i + 1 < n and s[i + 1] == ')':
					op += 1
					i += 1
					c = 0
			i += 1
		print(op, c)


from math import sqrt
from sys import stdin, stdout
for t in ' ' * int(input()):
	n = int(input())
	myStr = input()
	c = 0
	r = 0
	i = 0
	while i < n:
		if i == n - 1:
			r += 1
			break
		if myStr[i] == myStr[i + 1]:
			c += 1
			i += 2
		elif myStr[i] == '(' and myStr[i + 1] == ')':
			c += 1
			i += 2
		else:
			id = myStr.find(myStr[i], i + 2)
			if id > 0:
				newS = myStr[i:id + 1]
				if len(newS) == 3:
					c += 1
					i = i + 3
				else:
					for j in range(len(newS) // 2):
						if newS[j] != newS[(j + 1) * -1]:
							r = n - i
							i = -1
							break
					if i == -1:
						break
					c += 1
					i = id + 1
			else:
				r = n - i
				break
	print(c, r)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	prev = None
	ans = 0
	for i in range(n):
		if prev is None:
			prev = i
		elif s[i] == s[prev]:
			ans += 1
			prev = None
		elif i - prev == 1 and s[i] == ')' and (s[prev] == '('):
			ans += 1
			prev = None
	if prev is None:
		prev = n
	print(ans, n - prev)


def is_p(s):
	if str(s[0:int((len(s) + 1) / 2)]) == str(''.join(list(reversed(s[int(len(s) / 2):])))):
		return True
	return False

def is_r(s):
	if s[0] == '(' and s[len(s) - 1] == ')':
		t = 0
		for i in range(len(s)):
			if s[i] == '(':
				t += 1
			else:
				t -= 1
			if t < 0:
				return False
		if t == 0:
			return True
		else:
			return False
	return False
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	start = 0
	end = 1
	op = 0
	f = 0
	while end < len(s):
		if s[start] == '(':
			op += 1
			start += 2
			end = start + 1
		else:
			f = 1
		if f == 1:
			if s[end] == '(':
				end += 1
			else:
				op += 1
				start = end + 1
				end = start + 1
				f = 0
	print(op, len(s) - start)


def solver():
	n = int(input())
	for _ in range(n):
		l = int(input())
		word = input()
		c = 1
		furthest = 0
		operation = 0
		while c < l:
			current_word = word[c]
			if c - furthest > 0 and word[furthest] == current_word or word[furthest] + current_word == '()':
				furthest = c + 1
				operation += 1
			c += 1
		print(operation, l - furthest)
solver()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().rstrip()
	c = i = 0
	j = 1
	while i < n and j < n:
		if s[i] == s[j]:
			c += 1
			i = j + 1
			j = i + 1
		elif s[i] == '(' and s[j] == ')':
			c += 1
			i += 2
			j += 2
		else:
			j += 1
	if i >= n:
		left = 0
	else:
		left = n - i
	print(c, left)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [str for str in input()]
	(B, D) = (0, 0)
	C = A[::-1]
	i = 0
	while i < len(A) - 1:
		if A[i] == A[i + 1]:
			B += 1
			i += 2
			continue
		if A[i] == '(' and A[i + 1] == ')':
			B += 1
			i += 2
			continue
		j = -1
		for k in range(i + 1, N):
			if A[k] == ')':
				B += 1
				j = k
				break
		if j == -1:
			break
		i = j + 1
	if i < N:
		D = N - i
	print(B, D)


def balanced(str, n):
	_sum = 0
	maxi = 0
	for i in range(n):
		if str[i] == '(':
			_sum += 1
		else:
			_sum -= 1
		if _sum < 0:
			break
		if _sum == 0:
			maxi = i + 1
	return maxi
tt = int(input())
for i in range(tt):
	n = int(input())
	s = input()
	j = 0
	k = 1
	c = 0
	while j < n and k < n:
		if s[j] == ')' and s[k] == '(':
			k += 1
		else:
			j = k + 1
			k += 2
			c += 1
	print(c, n - j)


t = int(input())
for tt in range(0, t):
	n = int(input())
	s = input()
	ans = n
	res = 0
	posi = 0
	for i in range(0, n - 1):
		if posi >= n - 1:
			break
		i = posi
		if s[i] == '(':
			if s[i + 1] == ')':
				posi += 2
				ans -= 2
				res += 1
				continue
			if s[i + 1] == '(':
				posi += 2
				ans -= 2
				res += 1
				continue
		elif s[i + 1] == ')':
			posi += 2
			ans -= 2
			res += 1
			continue
		else:
			pos = 0
			for j in range(i + 1, n):
				if s[j] == ')':
					pos = j
					break
			if pos > i:
				ans -= pos - i + 1
				posi = pos + 1
				res += 1
				continue
			else:
				break
	print(res, ans)


def regular(x, s):
	if s[x - 1] == '(' and s[x] == ')':
		return True
	else:
		False

def palidrome(x, y, s):
	while x <= y and s[x] == s[y]:
		x += 1
		y -= 1
	if x >= y:
		return True
	else:
		return False

def ans():
	t = int(input())
	for i in range(0, t):
		tm = int(input())
		x = input()
		op = 0
		prev = 0
		j = 1
		while j < tm:
			if j - prev == 1 and regular(j, x):
				prev = j + 1
				op += 1
				j += 2
			elif palidrome(prev, j, x):
				op += 1
				prev = j + 1
				j += 2
			else:
				j += 1
		print(op, tm - prev)
ans()