A bracket sequence S is called *dense* if one of the following is true:
S is empty.
S = (X) where X is dense.

You are given a bracket sequence S. What is the minimum number of brackets you must remove to make it dense?

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

- The first line of input will contain a single integer T, the number of test cases. The description of the T test cases follows.
- The first line of each test case contains one integer N, denoting the length of the bracket sequence.
- The second line of each test case contains the bracket sequence S of length N.

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

For each test case, output on a new line the minimum number of brackets you must remove from S to make it dense.

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

$1 ≤ T ≤ 2 \cdot 10^{4}$
$1 ≤ N ≤ 3 \cdot 10^{5}$
- The sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$

----- Sample Input 1 ------ 
4
8
()(())()
6
((()))
10
()()()()()
8
((()))()

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

----- explanation 1 ------ 
Test case $1$: Remove the $2^{nd}$ and $7^{th}$ bracket to obtain ((())), which is dense.

Test case $2$: The given bracket sequence is already dense.

Test case $3$: Remove the $2^{nd}$, $4^{th}$, $7^{th}$, and $9^{th}$ bracket to obtain ((())), which is dense.

Test case $4$: Remove the last $2$ brackets to obtain ((())).

Source: codechef | Difficulty: MEDIUM
Tags: String algorithms

Data structures


Solutions:
n = int(input())
for i in range(n):
	r = int(input())
	a = input()
	(i, j) = (0, r - 1)
	remove = 0
	while i <= j:
		if a[i] == '(' and a[j] == ')':
			(i, j) = (i + 1, j - 1)
		elif a[i] == '(' and a[j] == '(':
			j = j - 1
			remove += 1
		elif a[i] == ')' and a[j] == ')':
			i = i + 1
			remove += 1
		else:
			(i, j) = (i + 1, j - 1)
			remove += 2
	print(remove)


import sys
input = sys.stdin.readline

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

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

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

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

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	S = insr()
	(bc, bo) = (S.count(')'), 0)
	for s in S:
		if s == '(':
			bo += 1
		else:
			bc -= 1
		if bo == bc:
			break
	ans.append(N - 2 * bc)
outplt(ans)


for _ in range(int(input())):
	n = int(input())
	string = input()
	count_c = string.count(')')
	count_o = 0
	for i in string:
		if count_o == count_c:
			break
		if i == '(':
			count_o += 1
		else:
			count_c -= 1
	print(n - count_o * 2)


for a0 in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	forward = list()
	backward = list()
	for i in range(n):
		if s[i] == '(':
			c += 1
		forward.append(c)
	c = 0
	for i in range(n):
		if s[i] == ')':
			c += 1
		backward.append(c)
	maxi = 0
	z = min(forward[i], backward[n - 1] - backward[i])
	for i in range(n):
		if maxi < min(forward[i], backward[n - 1] - backward[i]):
			maxi = min(forward[i], backward[n - 1] - backward[i])
	print(n - 2 * maxi)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	(i, j) = (0, N - 1)
	a = 0
	while i <= j:
		if S[i] == '(' and S[j] == ')':
			(i, j) = (i + 1, j - 1)
		elif S[i] == '(' and S[j] == '(':
			j = j - 1
			a += 1
		elif S[i] == ')' and S[j] == ')':
			i = i + 1
			a += 1
		else:
			(i, j) = (i + 1, j - 1)
			a += 2
	print(a)


tests = int(input())
for i in range(tests):
	length = int(input())
	string = input()
	opening = 0
	closing = string.count(')')
	gap = 10 ** 6
	total = 0
	for j in range(length):
		if string[j] == '(':
			opening += 1
		if string[j] == ')':
			closing -= 1
		temp_gap = abs(opening - closing)
		if temp_gap < gap:
			total = opening + closing
			gap = temp_gap
	if total & 1:
		total -= 1
	print(length - total)


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


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


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


for _ in range(int(input())):
	n = int(input())
	l1 = input()
	l = 0
	r = n - 1
	ans = 0
	while l < r:
		if l1[l] == '(':
			if l1[r] == ')':
				l = l + 1
				ans = ans + 2
			r = r - 1
		else:
			l = l + 1
	print(n - ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	close = s.count(')')
	opn = 0
	ans = n
	for i in s:
		if i == '(':
			opn += 1
			ans = min(ans, n - min(2 * opn, 2 * close))
		else:
			close -= 1
	print(ans)


from collections import Counter
t = int(input())
for i in range(t):
	o = 0
	n = int(input())
	ans = n
	s = str(input())
	c1 = Counter(s)
	c = c1[')']
	for i in range(n):
		if s[i] == '(':
			o += 1
			ans = min(ans, n - min(2 * o, 2 * c))
		else:
			c -= 1
	print(ans)


cases = int(input())
for _ in range(cases):
	n = int(input())
	string = input()
	low = 0
	remove = 0
	high = n - 1
	while low <= high:
		if string[low] == '(' and string[high] == ')':
			low += 1
			high -= 1
		elif string[low] == ')' and string[high] == '(':
			low += 1
			high -= 1
			remove += 2
		elif string[low] == '(' and string[high] == '(':
			high -= 1
			remove += 1
		else:
			low += 1
			remove += 1
	print(remove)


def find(n, s):
	(left, right) = (0, n - 1)
	ans = 0
	while left <= right:
		if s[left] == '(' and s[right] == ')':
			left += 1
			right -= 1
		elif s[left] == '(' and s[right] == '(':
			ans += 1
			right -= 1
		elif s[left] == ')' and s[right] == ')':
			ans += 1
			left += 1
		elif s[left] == ')' and s[right] == '(':
			ans += 2
			left += 1
			right -= 1
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	find(n, s)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(l, r) = (0, len(s) - 1)
	c = 0
	while l <= r:
		if s[l] == '(' and s[r] == ')':
			l += 1
			r -= 1
		elif s[l] == '(' and s[r] == '(':
			c += 1
			r -= 1
		elif s[l] == ')' and s[r] == ')':
			c += 1
			l += 1
		elif s[l] == ')' and s[r] == '(':
			c += 2
			l += 1
			r -= 1
	print(c)


from bisect import *
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(fr, bk) = ([0] * n, [0] * n)
	(fr[0], bk[-1]) = (0 + (s[0] == '('), 0 + (s[-1] == ')'))
	for i in range(1, n):
		fr[i] = fr[i - 1] + (s[i] == '(')
	for i in range(n - 2, -1, -1):
		bk[i] = bk[i + 1] + (s[i] == ')')
	max_ = 0
	for i in range(n):
		max_ = max(max_, 2 * min(fr[i], bk[i]))
	print(n - max_)


def removeBrackets(s):
	(l, r) = (0, len(s) - 1)
	count = 0
	while l <= r:
		if s[l] == '(' and s[r] == ')':
			l += 1
			r -= 1
		elif s[l] == '(' and s[r] == '(':
			count += 1
			r -= 1
		elif s[l] == ')' and s[r] == ')':
			count += 1
			l += 1
		elif s[l] == ')' and s[r] == '(':
			count += 2
			l += 1
			r -= 1
	return count
for _ in range(int(input())):
	n = int(input())
	print(removeBrackets(input()))


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	j = n - 1
	c = 0
	while i <= j:
		if s[i] == '(' and s[j] == ')':
			i += 1
			j -= 1
			continue
		if s[i] == ')':
			i += 1
			c += 1
		if s[j] == '(':
			j -= 1
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(ans, open, closed) = (n, 0, s.count(')'))
	for c in s:
		if c == '(':
			open += 1
			ans = min(ans, n - 2 * min(open, closed))
		else:
			closed -= 1
	print(ans)


import re

def ans(s):
	k = ''.join(reversed(str(s)))
	return k
t = int(input())
while t > 0:
	a = int(input())
	s = str(input())
	ans = a
	ope = 0
	clo = s.count(')')
	for i in s:
		if i == '(':
			ope += 1
			ans = min(ans, a - 2 * min(ope, clo))
		else:
			clo -= 1
	print(ans)
	t -= 1


for i in range(int(input())):
	n = int(input())
	s = str(input())
	st = 0
	end = n - 1
	count = 0
	while st <= end:
		if s[st] == '(' and s[end] == ')':
			st += 1
			end -= 1
		elif s[st] == ')' and s[end] == ')':
			count += 1
			st += 1
		elif s[st] == '(' and s[end] == '(':
			count += 1
			end -= 1
		elif s[st] == ')' and s[end] == '(':
			count += 2
			end -= 1
			st += 1
	print(count)


for _ in range(int(input())):
	a = int(input())
	n = input()
	i = 0
	j = a - 1
	c = 0
	while i <= j:
		if n[i] == '(' and n[j] == ')':
			i += 1
			j -= 1
		elif n[i] == ')':
			i += 1
			c += 1
		elif n[j] == '(':
			j -= 1
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = input()
	i = 0
	j = len(a) - 1
	count = 0
	while i < j:
		if a[i] == '(' and a[j] == ')':
			i += 1
			j -= 1
			count += 1
		elif a[i] == '(' and a[j] == '(':
			j -= 1
		elif a[i] == ')' and a[j] == ')':
			i += 1
		else:
			i += 1
			j -= 1
	print(n - 2 * count)


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


tc = int(input())
for tc in range(tc):
	n = int(input())
	s = input()
	l = 0
	r = n // 2
	ans = 0
	while l <= r:
		mid = (l + r) // 2
		isopen = True
		cntopen = 0
		cntclose = 0
		for i in range(n):
			if isopen and cntopen >= mid:
				isopen = False
			if s[i] == '(' and isopen:
				cntopen += 1
			if s[i] == ')' and isopen == False:
				cntclose += 1
		if cntopen >= mid and cntclose >= mid:
			ans = 2 * mid
			l = mid + 1
		else:
			r = mid - 1
	print(n - ans)


from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))

def answer():
	prefix = [0]
	for i in range(n):
		prefix.append(prefix[-1] + (a[i] == '('))
	suffix = [0]
	for i in range(n - 1, -1, -1):
		suffix.append(suffix[-1] + (a[i] == ')'))
	suffix = suffix[::-1]
	ans = n
	for i in range(n):
		ans = min(ans, n - 2 * min(prefix[i + 1], suffix[i]))
	return ans
for T in range(int(input())):
	n = int(input())
	a = input().strip()
	print(answer())


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	s = input()
	open_b = [0 for i in range(n)]
	closed_b = [0 for i in range(n)]
	for i in range(n):
		if s[i] == '(':
			open_b[i] = open_b[i - 1] + 1
		else:
			open_b[i] = open_b[i - 1]
	for i in range(n - 1, -1, -1):
		if s[i] == ')':
			closed_b[i] = closed_b[(i + 1) % n] + 1
		else:
			closed_b[i] = closed_b[(i + 1) % n]
	ans = 0
	for i in range(n):
		ans = max(ans, min(open_b[i], closed_b[i]))
	print(n - 2 * ans)


t = int(input())
for i in range(t):
	sum = 0
	x = int(input())
	s = input()
	count = x + 1
	l1 = [0 for i in range(x)]
	l2 = [0 for i in range(x)]
	for i in range(x):
		if s[i] == '(':
			l1[i] += 1
		if i > 0:
			l1[i] += l1[i - 1]
	for i in range(x - 1, -1, -1):
		if s[i] == ')':
			l2[i] += 1
		if i < x - 1:
			l2[i] += l2[i + 1]
		count = min(count, x - 2 * min(l1[i], l2[i]))
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	str = input()
	l = 0
	r = n - 1
	ans = 0
	while l < r:
		if str[l] == '(':
			if str[r] == ')':
				l += 1
				ans += 2
			r -= 1
		else:
			l += 1
	print(n - ans)


for i in range(int(input())):
	n = int(input())
	str1 = input()
	left = 0
	right = n - 1
	answer = 0
	while left < right:
		if str1[left] == '(':
			if str1[right] == ')':
				left += 1
				answer += 2
			right -= 1
		else:
			left += 1
	print(n - answer)


t = int(input())
for tt in range(t):
	h = int(input())
	s = input()
	dense = 0
	count = 0
	j = h
	if h == 1:
		print(1)
	elif h == 0:
		print(0)
	else:
		while count < j - 1:
			if s[count] == '(' and s[j - 1] == ')':
				dense += 2
				count += 1
				j -= 1
			elif s[count] == '(' and s[j - 1] == '(':
				j -= 1
			elif s[count] == ')' and s[j - 1] == ')':
				count += 1
			else:
				count += 1
				j -= 1
		print(h - dense)


for _ in range(int(input())):
	n = int(input())
	s = input()
	open = 0
	close = 0
	ans = 9999999
	for i in range(n):
		if s[i] == ')':
			close += 1
	for i in range(n):
		if s[i] == '(':
			open += 1
		if s[i] == ')':
			close -= 1
		ans = min(ans, n - min(2 * open, 2 * close))
	print(ans)


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


try:
	for _ in range(int(input())):
		n = int(input())
		s = input().strip()
		r = s.count(')')
		l = n - r
		c = 0
		res = -1
		for i in range(n):
			if s[i] == '(':
				c += 1
				res = max(res, min(c, r))
			else:
				r -= 1
		res = max(res, min(c, r))
		print(n - 2 * res)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	s = input()
	count = 0
	f = n - 1
	b = 0
	while b < f:
		if s[b] == '(':
			if s[f] == ')':
				b += 1
				count += 2
			f -= 1
		else:
			b += 1
	print(n - count)


for i in range(int(input())):
	n = int(input())
	s = list(input())
	op = 0
	cl = s.count(')')
	ans = n
	for c in s:
		if c == '(':
			op = op + 1
			ans = min(ans, n - min(2 * op, 2 * cl))
		else:
			cl = cl - 1
	print(ans)


for i in range(int(input())):
	N = int(input())
	s = input()
	if N == 1:
		print(1)
	else:
		count = 0
		f = 0
		b = N - 1
		while f < b:
			if s[f] == '(':
				if s[b] == ')':
					f += 1
					count += 2
				b -= 1
			else:
				f += 1
		print(N - count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	i = 0
	j = n - 1
	d = 0
	while i < j:
		if l[i] == '(':
			if l[j] == ')':
				i += 1
				d += 2
			j = j - 1
		else:
			i = i + 1
	if n == 1:
		print('1')
	else:
		print(n - d)


for _ in range(int(input())):
	n = int(input())
	a = input()
	p2 = n - 1
	p1 = 0
	count = 0
	while p1 <= p2:
		if a[p1] == '(' and a[p2] == ')':
			p1 += 1
			p2 -= 1
		elif a[p1] == '(' and a[p2] == '(':
			p2 -= 1
			count += 1
		elif a[p1] == ')' and a[p2] == ')':
			p1 += 1
			count += 1
		elif a[p1] == a[p2]:
			count += 1
		else:
			count += 2
			p1 += 1
			p2 -= 1
	print(count)


n = int(input())
for i in range(n):
	len_bracket = int(input())
	if len_bracket == 1:
		print(1)
	bracket = input()
	first = 0
	last = len_bracket - 1
	dense = 0
	while first < last:
		if bracket[first] == '(':
			if bracket[last] == ')':
				first += 1
				dense += 2
			last -= 1
		else:
			first += 1
	if len_bracket != 1:
		print(len_bracket - dense)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	if n == 1:
		print(1)
	else:
		i = 0
		j = n - 1
		dense = 0
		while i < j:
			if s[i] == '(':
				if s[j] == ')':
					i += 1
					dense += 2
				j -= 1
			else:
				i += 1
		print(n - dense)


t = int(input())
for i in range(t):
	n = int(input())
	arr = str(input())
	l = 0
	r = n // 2
	ans = 0
	while l <= r:
		mid = (l + r) // 2
		isOpen = True
		cntOpen = 0
		cntClosed = 0
		for i in range(n):
			if isOpen and cntOpen >= mid:
				isOpen = False
			if arr[i] == '(' and isOpen:
				cntOpen += 1
			if arr[i] == ')' and (not isOpen):
				cntClosed += 1
		if cntOpen >= mid and cntClosed >= mid:
			ans = 2 * mid
			l = mid + 1
		else:
			r = mid - 1
	print(n - ans)


def power(x, n):
	ans = 1
	while n > 0:
		if n % 2 == 1:
			ans = ans * x
			n = n - 1
		else:
			x = x * x
			n = n // 2
	return ans
t = int(input())
mod = 10 ** 9 + 7
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	i = 0
	j = len(s) - 1
	ans = 0
	while i < j:
		if s[i] == '(' and s[j] == ')':
			i += 1
			j -= 1
			continue
		if s[i] == ')':
			i += 1
			ans += 1
		if s[j] == '(':
			j -= 1
			ans += 1
	if i == j:
		ans += 1
	print(ans)


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

def isValid(s, target):
	i = ct = 0
	while i < len(s) and ct < target:
		ct += s[i] == '('
		i += 1
	ct = 0
	while i < len(s) and ct < target:
		ct += s[i] == ')'
		i += 1
	return ct == target

def binarySearch(s):
	(l, r) = (0, len(s) // 2)
	res = 0
	while l <= r:
		mid = (r + l) // 2
		if isValid(s, mid):
			res = mid
			l = mid + 1
		else:
			r = mid - 1
	return res

def solve():
	n = int(input())
	s = input()
	res = binarySearch(s)
	return len(s) - 2 * res

def main():
	sys.setrecursionlimit(10 ** 8)
	for _ in range(int(input())):
		result = solve()
		print(result)
main()


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		S = input()
		if N == 1:
			print(1)
		else:
			(i, j, dense) = (0, N - 1, 0)
			while i < j:
				if S[i] == '(':
					while j > i:
						if S[j] == ')':
							dense += 2
							j -= 1
							break
						j -= 1
				i += 1
			print(N - dense)
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = []
	r = []
	for i in range(n):
		if s[i] == '(':
			l.append(i)
		else:
			r.append(i)
	size_l = len(l)
	size_r = len(r)
	remove = 0
	if size_l == size_r:
		for i in range(size_l):
			if l[i] > r[size_l - 1 - i]:
				remove += 2
	elif size_l > size_r:
		remove += size_l - size_r
		for i in range(size_r):
			if l[i] > r[size_r - 1 - i]:
				remove += 2
	else:
		remove += size_r - size_l
		for i in range(size_l):
			if l[i] > r[size_r - 1 - i]:
				remove += 2
	print(remove)


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