Last summer, Feluda gifted Lalmohan-Babu a balanced bracket sequence $s$ of length $2 n$.

Topshe was bored during his summer vacations, and hence he decided to draw an undirected graph of $2 n$ vertices using the balanced bracket sequence $s$. For any two distinct vertices $i$ and $j$ ($1 \le i < j \le 2 n$), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment $s[i \ldots j]$ forms a balanced bracket sequence.

Determine the number of connected components in Topshe's graph.

See the Notes section for definitions of the underlined terms.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of opening brackets in string $s$.

The second line of each test case contains a string $s$ of length $2 n$ — a balanced bracket sequence consisting of $n$ opening brackets "(", and $n$ closing brackets ")".

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, output a single integer — the number of connected components in Topshe's graph.


-----Examples-----

Input
4
1
()
3
()(())
3
((()))
4
(())(())
Output
1
2
3
3


-----Note-----

Sample explanation:

In the first test case, the graph constructed from the bracket sequence (), is just a graph containing nodes $1$ and $2$ connected by a single edge.

In the second test case, the graph constructed from the bracket sequence ()(()) would be the following (containing two connected components):

Definition of Underlined Terms:

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $+$ and $1$. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.

The subsegment $s[l \ldots r]$ denotes the sequence $[s_l, s_{l + 1}, \ldots, s_r]$.

A connected component is a set of vertices $X$ such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to $X$ violates this rule.

Difficulty: EASY
Tags: Spanning trees

Graph algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
for s in [*open(0)][2::2]:
	print(len(s) // 2 - s.count(')('))


for i in [*open(0)][2::2]:
	x = ')'
	ans = 1
	for j in i:
		if j == '(' and x == '(':
			ans += 1
		x = j
	print(ans)


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	n = int(input())
	instring = input()
	levels = []
	lastchar = '('
	groups = 1
	for char in instring[1:-1]:
		if char == '(':
			if lastchar == '(':
				groups += 1
		lastchar = char
	print(groups)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = input()
	print(1 + s.count('(') - s.count('()'))
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
in_il = lambda : list(map(int, input().split()))
in_sl = lambda : input().split()
in_i = lambda : int(input())
MAX_INT = float('inf')

def solve():
	n = in_i()
	s = input()
	ans = 1
	for i in range(1, len(s)):
		if s[i] == '(' and s[i - 1] == '(':
			ans += 1
	print(ans)
for _ in range(in_i()):
	solve()


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = sys.stdin.readline().strip()
	ans = n
	for i in range(n * 2 - 1):
		if a[i] == ')' and a[i + 1] == '(':
			ans -= 1
	print(ans)


import itertools
import sys
import math
from bisect import *
from collections import deque
input = sys.stdin.readline
from collections import defaultdict
from collections import Counter
for k in range(int(input())):
	n = int(input())
	s = str(input())
	j = 2 * n - 1
	i = 0
	ans = n + 1
	while True:
		if i >= j:
			break
		if s[i + 1] == ')' and s[i] == '(':
			i += 2
			ans -= 1
		elif s[j] == ')' and s[j - 1] == '(':
			j -= 2
			ans -= 1
		else:
			i += 1
			j -= 1
	print(ans)


output = ''
for caseno in range(int(input())):
	n = input()
	l = input()
	prev = l[0]
	answer = 1
	for i in l[1:]:
		if i == '(':
			answer += prev == '('
		prev = i
	output += str(answer) + '\n'
print(output)


import sys

def read():
	cases = int(sys.stdin.readline())
	for k in range(cases):
		open = int(sys.stdin.readline())
		parens = sys.stdin.readline()
		solve(parens, open)

def solve(parens, open):
	count = 0
	stack = [False] * (open + 1)
	stack_ind = 0
	for k in range(len(parens)):
		if parens[k] == '(':
			if stack[stack_ind] == False:
				stack[stack_ind] = True
				count += 1
			stack_ind += 1
		else:
			stack[stack_ind] = False
			stack_ind -= 1
	print(count)
read()


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

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

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

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

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

def solve():
	n = int_num()
	s = instr()
	level = 0
	a = []
	for c in s:
		if c == '(':
			level += 1
			a.append(level)
		else:
			level -= 1
	ans = 0
	b = [a[0]]
	for i in range(1, len(a)):
		if a[i] > b[-1]:
			b.append(a[i])
		else:
			while a[i] < b[-1]:
				ans += 1
				b.pop()
	ans += len(b)
	print(ans)

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


print(*[int(input()) - input().count(')(') for i in range(int(input()))], sep='\n')


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	S = input().strip()
	pos = {0: [-1]}
	v = 0
	ans = 0
	for i in range(2 * n):
		if S[i] == '(':
			v += 1
			if v not in pos:
				pos[v] = []
			if S[i + 1] == '(':
				pos[v].append(i)
		else:
			while pos[v]:
				pos[v].pop()
			v -= 1
			if v not in pos:
				pos[v] = []
			elif len(pos[v]) == 1:
				ans += 1
			if i < 2 * n - 1 and S[i + 1] == '(':
				pos[v].append(i)
	return ans
for _ in range(int(input())):
	print(solve())


from sys import stdin, stdout
import sys

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

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
while t:
	t -= 1
	n = get_ints()
	s = get_string()
	ans = int(1)
	for i in range(1, len(s)):
		if s[i - 1] == '(' and s[i] == '(':
			ans += 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	c = 1
	t = 0
	a = []
	for i in s:
		if i == '(':
			a.append('(')
			t = 0
		else:
			a.pop()
			c += t
			if len(a) > 0:
				t = 1
	print(c)


import sys
import math
from collections import Counter
from collections import defaultdict

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

def get_string():
	return sys.stdin.readline().strip()

def solve(n, arr):
	cnt = 0
	for i in range(len(arr) - 1):
		if arr[i] == '(' and arr[i + 1] == ')':
			cnt += 1
	return n - cnt + 1
t = int(input())
for _ in range(t):
	n = get_ints()
	st = get_string()
	print(solve(n[0], st))


import sys
input = sys.stdin.readline
print = sys.stdout.write
for _ in range(int(input())):
	(n, s) = (int(input()), input())
	st = []
	end = [0] * (2 * n)
	a = []
	for i in range(2 * n):
		if s[i] == '(':
			st.append(i)
			a.append(i)
		else:
			end[st.pop()] = i
	ans = n
	for i in range(n):
		s1 = a[i]
		e1 = end[s1]
		s2 = e1 + 1
		if s2 < 2 * n:
			e2 = end[s2]
			if e1 < s2 < e2:
				ans -= 1
	print(str(ans) + '\n')


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		st = [-1]
		dit = {}
		gp = defaultdict(list)
		for i in range(2 * n):
			if s[i] == '(':
				st.append(i)
			else:
				a = st.pop()
				gp[a].append(i)
				gp[i].append(a)
				if a - 1 in dit:
					gp[i].append(dit[a - 1])
					gp[dit[a - 1]].append(i)
				dit[i] = a
		ans = 0
		visit = set()

		def fun(i):
			if i in visit:
				return
			visit.add(i)
			for e in gp[i]:
				fun(e)
		for i in range(2 * n):
			if i not in visit:
				ans += 1
				fun(i)
		print(ans)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


for pratyush in range(int(input())):
	n = int(input())
	s = input()
	print(n - s.count('()') + 1)


def solve():
	n = int(input())
	s = input()
	print(n - s.count(')('))
t = int(input())
for _ in range(t):
	solve()


def cal(n, s):
	if n == 1:
		return 1
	t = 0
	ans = 1
	p = []
	for i in s:
		if i == '(':
			t += 1
			p.append(t)
		else:
			t -= 1
	for i in range(1, len(p)):
		if p[i] > p[i - 1]:
			ans += 1
	return ans
for jj in range(int(input())):
	n = int(input())
	s = input()
	print(cal(n, s))


for _ in range(int(input())):
	n = int(input())
	s = input()
	print(n - s.count(')('))


t = int(input())
for _ in range(t):
	input()
	s = input()
	len_s = len(s) // 2
	print(len_s - s.count(')('))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(n - s.count(')('))


for i in range(int(input())):
	print(int(input()) - input().count(')('))


for j in range(int(input())):
	print(1 + int(input()) - input().count('()'))


for _ in range(int(input())):
	n = int(input())
	a = input()
	print(n - a.count(')('))


for _ in range(int(input())):
	a = int(input())
	b = input()
	print(a - b.count('()') + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	print(n - s.count('()') + 1)


for _ in range(int(input())):
	print(int(input()) - str(input()).count(')('))


for tc in range(int(input())):
	n = int(input())
	seq = input()
	print(1 + seq.count('(') - seq.count('()'))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(1 + s.count('(') - s.count('()'))


for loop in range(int(input())):
	n = int(input())
	s = input()
	print(1 + s.count('(') - s.count('()'))


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = 1
	for i in range(2 * n - 1):
		if s[i] == '(' and s[i + 1] == '(':
			ans += 1
	print(ans)


for a in range(int(input())):
	n = int(input())
	b = input()
	count = 1 if b else 0
	prev = 0
	for c in b:
		if prev:
			if c == '(':
				count += 1
			else:
				prev = 0
		elif c == '(':
			prev = 1
	print(count)


for tc in range(int(input())):
	N = int(input())
	S = input()
	ans = 1
	for i in range(2 * N - 1):
		if S[i] == ')' and S[i + 1] == ')':
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cur = 0
	runner = -1
	res = n
	for c in s:
		if c == '(':
			cur += 1
			if cur <= runner:
				res -= 1
			runner = cur
		else:
			cur -= 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 1
	for i in range(2 * n - 1):
		if s[i] == '(' and s[i + 1] == '(':
			ans += 1
	print(ans)


test = int(input())
for t in range(test):
	n = int(input())
	A = input()
	for i in range(2 * n - 1):
		if A[i] == ')' and A[i + 1] == '(':
			n -= 1
	print(n)


for _ in range(int(input())):
	n = int(input())
	s = input()
	st = []
	empty = 0
	ans = 1 + s.count('(')
	minus = s.count('()')
	print(ans - minus)


def sol():
	n = int(input())
	s = input()
	cnt = 0
	for i in range(len(s) - 1):
		if s[i] == '(' and s[i + 1] == '(':
			cnt += 1
	print(cnt + 1)
t = int(input())
for i in range(t):
	sol()


for t in range(int(input())):
	n = int(input())
	bracket = input()
	count = 0
	for i in range(2 * n - 1):
		if bracket[i] == ')' and bracket[i + 1] == '(':
			count += 1
	print(n - count)


def balanced_brackets(s):
	new_str = s.replace(')(', '')
	return sum([ch == '(' for ch in new_str])
num_tests = int(input())
for _ in range(num_tests):
	n = int(input())
	s = input()
	print(balanced_brackets(s))


def main():
	for t in range(int(input())):
		n = int(input())
		s = input()
		c = ''
		ans = 0
		for i in range(2 * n):
			if s[i] == '(':
				if c != ')':
					ans += 1
			c = s[i]
		print(ans)
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	stack = []
	ans = 0
	for i in range(len(s) - 1):
		if s[i] == ')' and s[i + 1] == ')':
			ans += 1
	print(ans + 1)


number_of_tests = int(input())
for _ in range(number_of_tests):
	n = int(input())
	brackets = input()
	i = 0
	prev = '('
	result = 0
	while n > 0:
		if prev == '(' and brackets[i] == '(':
			result += 1
		if brackets[i] == '(':
			n -= 1
		prev = brackets[i]
		i += 1
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	count = 0
	for j in range(2 * n):
		if a[j] == '(' and a[j + 1] == ')':
			count += 1
	print(n - count + 1)


for _ in range(int(input())):
	n = int(input())
	l = input()
	lst = []
	c = 0
	for i in range(1, 2 * n):
		if l[i - 1] + l[i] == ')(':
			c += 1
	print(n - c)


tc = int(input())
for i in range(tc):
	n = int(input())
	lst = input()
	out = 0
	for i in range(2 * n - 1):
		if lst[i] == '(' and lst[i + 1] == ')':
			out += 1
	print(n - out + 1)


n = int(input())
for p in range(0, n):
	m = int(input())
	a = input()
	oo = 0
	for j in range(0, 2 * m - 1):
		if a[j] == '(':
			if a[j + 1] == '(':
				oo = oo + 1
	print(oo + 1)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = input()
	ans = 0
	for j in range(0, len(a) - 1):
		if a[j] == '(' and a[j + 1] == '(':
			ans = ans + 1
	print(ans + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = 0
	for i in range(0, 2 * n - 1):
		if s[i] == '(' and s[i + 1] == ')':
			c += 1
	print(n - c + 1)


n = int(input())
while n > 0:
	N = int(input())
	s = input()
	k = 0
	ans = 1
	for i in range(2 * N):
		if s[i] == '(':
			k = k + 1
			if k >= 2:
				ans = ans + 1
		else:
			k = 0
	print(ans)
	n = n - 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	for i in range(2 * n - 1):
		if s[i] == ')' and s[i + 1] == ')':
			cnt += 1
	print(cnt + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	su = 0
	d = set()
	cnt = n
	prev = float('-inf')
	for k in s:
		if k == '(':
			su += 1
			if su in d and prev >= su:
				cnt -= 1
			d.add(su)
			prev = su
		else:
			su -= 1
	print(cnt)


def solve(n, bracket):
	num_components = 2 * n
	stack = []
	right_connect = {}
	for bracket_index in range(2 * n):
		if bracket[bracket_index] == '(':
			stack.append(('(', bracket_index))
		else:
			num_components -= 1
			right_connect[bracket_index] = stack.pop()[1]
	for right in right_connect:
		if right_connect[right] >= 1 and bracket[right_connect[right] - 1] == ')':
			num_components -= 1
	return num_components
t = int(input())
for _ in range(t):
	n = int(input())
	bracket = input()
	print(solve(n, bracket))


import sys

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

def get_string():
	return sys.stdin.readline().strip()

def fun(arr):
	c = 0
	for i in range(len(arr) - 1):
		if arr[i] == '(' and arr[i + 1] == ')':
			c += 1
	return c
l = int(input())
for _ in range(l):
	n = int(input())
	arr = get_string()
	z = fun(arr)
	print(n - z + 1)


t = int(input())
while t:
	n = int(input())
	s = input()
	sum = 0
	for i in range(2 * n - 1):
		if s[i] == '(' and s[i + 1] == ')':
			sum += 1
	print(n - sum + 1)
	t -= 1


import sys
sys.setrecursionlimit(10 ** 7)
for _ in range(int(input())):
	n = int(input())
	s = input()
	n *= 2
	ans = 1
	for i in range(1, n):
		ans += s[i] == s[i - 1] == '('
	print(ans)


t = int(input())
while t > 0:
	a = []
	ans = 1
	n = int(input())
	s = input()
	for x in s:
		a.append(x)
	for x in range(0, len(a) - 1):
		if a[x] == ')' and a[x + 1] == ')':
			ans += 1
	print(ans)
	t -= 1


n = int(input())
for i in range(n):
	trash = int(input())
	miew = input()
	balance = 0
	groups = 0
	recently_closed = False
	for j in range(len(miew)):
		char = miew[j]
		if char == '(':
			balance += 1
			recently_closed = False
		else:
			if balance > 0 and recently_closed:
				groups += 1
			if balance > 0:
				balance -= 1
				recently_closed = True
			else:
				groups += 1
	groups += balance + 1
	print(groups)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	ans = n + 1
	stack = []
	for char in s:
		if char == '(':
			stack.append(['(', -1])
		else:
			(_, cnt) = stack.pop()
			if cnt > 0:
				ans -= cnt
			if len(stack) == 0:
				ans -= 1
			else:
				stack[-1][1] += 1
	print(ans)


t = int(input())
while t:
	p = int(input())
	s = input()
	r = 0
	check = 0
	while r < 2 * p - 1:
		if s[r + 1] == ')' and s[r] == '(':
			check += 1
		r += 1
	print(1 - check + p)
	t -= 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	ans = 0
	s = input()
	st = []
	ans1 = 0
	flag = 0
	for i in range(2 * n):
		if s[i] == '(':
			if st and flag == 0:
				ans += 1
			st.append('(')
			flag = 0
		else:
			st.pop()
			flag = 1
	print(ans - ans1 + 1)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	ans = 0
	for x in range(2 * n - 1):
		if s[x] == '(' and s[x + 1] == ')':
			ans += 1
	print(n - ans + 1)


for testcase in range(int(input())):
	n = int(input()) * 2
	s = input()
	stack = [False] * (n // 2 + 5)
	depth = 0
	ans = 0
	for i in range(n):
		if s[i] == '(':
			depth += 1
		else:
			stack[depth] = False
			depth -= 1
			if not stack[depth]:
				ans += 1
				stack[depth] = True
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	c = {0: 0}
	d = 0
	tot = n
	for p in s:
		if p == '(':
			d += 1
			c[d] = 0
		else:
			tot -= max(0, c[d] - 1)
			d -= 1
			c[d] += 1
	print(tot - c[0] + 1)