You are given a bracket sequence $s$ of length $n$, where $n$ is even (divisible by two). The string $s$ consists of $\frac{n}{2}$ opening brackets '(' and $\frac{n}{2}$ closing brackets ')'.

In one move, you can choose exactly one bracket and move it to the beginning of the string or to the end of the string (i.e. you choose some index $i$, remove the $i$-th character of $s$ and insert it before or after all remaining characters of $s$).

Your task is to find the minimum number of moves required to obtain regular bracket sequence from $s$. It can be proved that the answer always exists under the given constraints.

Recall what the regular bracket sequence is:

  "()" is regular bracket sequence;  if $s$ is regular bracket sequence then "(" + $s$ + ")" is regular bracket sequence;  if $s$ and $t$ are regular bracket sequences then $s$ + $t$ is regular bracket sequence. 

For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2000$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($2 \le n \le 50$) — the length of $s$. It is guaranteed that $n$ is even. The second line of the test case containg the string $s$ consisting of $\frac{n}{2}$ opening and $\frac{n}{2}$ closing brackets.


-----Output-----

For each test case, print the answer — the minimum number of moves required to obtain regular bracket sequence from $s$. It can be proved that the answer always exists under the given constraints.


-----Example-----
Input
4
2
)(
4
()()
8
())()()(
10
)))((((())

Output
1
0
1
3



-----Note-----

In the first test case of the example, it is sufficient to move the first bracket to the end of the string.

In the third test case of the example, it is sufficient to move the last bracket to the beginning of the string.

In the fourth test case of the example, we can choose last three openning brackets, move them to the beginning of the string and obtain "((()))(())".

Difficulty: introductory

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    s = input()
    st = 0
    fans = 0
    for x in s:
        if x == ')':
            st -= 1
        else:
            st += 1
        if st < 0:
            fans += 1
            st = 0
    print(fans)

import sys
# sys.setrecursionlimit(10**6) 
input=sys.stdin.readline
t=int(input())
for t1 in range(t):
    n=int(input())
    s=input()
    s=s.strip()
    l=[]
    l.append(s[0])
    for i in range(1,n):
        if(s[i]==")" and len(l)>0 and l[-1]=="("):
            l.pop()
        else:
            l.append(s[i])
    print(len(l)//2)




# for _ in range(1):
for _ in range(int(input())):
    # a, b = map(int, input().split())
    n = int(input())
    # arr = list(map(int, input().split()))
    s = input()
    bal = 0
    minbal = 0
    for i in range(n):
        if s[i] == ')':
            bal -= 1
        else:
            bal += 1
        minbal = min(minbal, bal)
    print(-minbal)

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

for _ in range(int(input())):
    n = int(input())
    ar = list(input())
    kek = 0
    ans = 0
    for i in range(n):
        if ar[i] == '(':
            kek += 1
        else:
            kek -= 1
        if kek < 0:
            kek += 1
            ans += 1
    print(ans)

def unbalancing(s):
    x = 0
    retvalue = 0
    for c in s:
        if c == '(':
            x += 1
        else:
            x -= 1
        retvalue = min(retvalue, x)
    return retvalue

for _ in range(int(input())):
    n = int(input())
    s = input()
    print(-unbalancing(s))


for testcase in range(int(input())):
    n = int(input())
    s = input().strip()
    ans = 0
    sum = 0
    for ch in s:
        if ch == '(':
            sum += 1
        else:
            sum -= 1
        ans = max(ans, -sum)
    print(ans)


import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n=int(input())
    S=input().strip()

    MIN=0
    NOW=0
    for s in S:
        if s=="(":
            NOW+=1
        else:
            NOW-=1
            MIN=min(NOW,MIN)

    print(-MIN)

    


# Created by: WeirdBugsButOkay
# 28-06-2020, 20:12:37

import math

def solve() :
    n = int(input())
    s = input()
    #n = len(s)
    bal = 0
    ans = 0
    for i in range (0, n) :
        if s[i] == '(' :
            bal += 1
        else :
            bal -= 1
            ans = max(ans, -bal)
    print(ans)

t = 1
t = int(input())
for _ in range (0, t) :
    solve()


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


for _ in range(val()):
    n = val()
    s = st()
    open = 0
    ans = 0
    for i in s:
        if i == '(':
            open += 1
        elif open > 0:
            open -= 1
        else:
            ans += 1
    print(ans)

t = int(input())
for _ in range(t):
    n = int(input())
    s = input().strip()
    curr = 0
    out = 0
    for c in s:
        if c == '(':
            curr += 1
        else:
            if curr:
                curr -= 1
            else:
                out += 1
    print(out)




a=int(input())
for i in range(a):
    r=int(input())
    s=input()
    score=0
    count=0
    for i in range(len(s)):
        if(s[i]==')'):
            score-=1
            if(score<0):
                score=0
                count+=1
        else:
            score+=1
    print(count)


t = int(input())
for case in range(t):
    n = int(input())
    s = input()
    low = 0
    ht = 0
    for i in range(n):
        if s[i] == ')':
            ht -= 1
        else:
            ht += 1
        low = min(low, ht)
    ans = -low
    print(ans)


tt = int(input())

for loop in range(tt):

    n = int(input())
    s = input()
    d = 0

    ans = 0
    for i in s:
        if i == "(":
            d += 1
        else:
            d -= 1

        if d < 0:
            ans += 1
            d = 0

    print (ans)


import sys
input = sys.stdin.readline
from  math import ceil

answer = []
for kek in range(int(input())):
    n = int(input())
    s = input()
    a = 0
    m = 0
    for i in s:
        if i == '(':
            a += 1
        if i == ')':
            a -= 1
        m = min(a, m)
    answer.append(-m)
print(*answer, sep='\n')


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	p = [0]
	for x in s:
		if x == '(':
			p.append(p[-1] + 1)
		else:
			p.append(p[-1] - 1)
	print(-min(p))


def solve():
    n = int(input())
    s = input()
    n1 = 0
    for i in s:
        if i == "(":
            n1 += 1
        else:
            n1 -= 1
        n1 = max(n1, 0)
    print(n1)
for i in range(int(input())):
    solve()

t=int(input())
def fun(n,a):
    ans=0
    count=0
    i=0
    while i<n:
        if a[i]=="(":
            count+=1
        else:
            count-=1
        i+=1
        if count<0:
            ans+=1
            count+=1
    print(int(ans))
while t:
    t-=1
    n=int(input())
    a=input()
    fun(n,a)


for nt in range(int(input())):
	n = int(input())
	s = input()
	stack = []
	ans = 0
	for i in range(n):
		if len(stack)==0:
			if s[i]==")":
				s += ")"
				ans += 1
			else:
				stack.append("(")
		else:
			if s[i]==")":
				stack.pop()
			else:
				stack.append("(")
	print (ans)

t=int(input())
for you in range(t):
    n=int(input())
    s=input()
    curr=0
    ans=0
    for i in s:
        if(i=='('):
            curr+=1
        else:
            curr-=1
        if(curr<0):
            ans+=1
            curr=0
    print(ans)


t = int(input())
for _ in range(t):
    n = int(input())
    s = input()

    left = 0
    ans = 0
    for x in s:
        if x == '(':
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                ans += 1

    print(ans)


for _ in range(int(input())):
    n=int(input())
    s=input()
    q=0
    ans=0
    for i in s:
        if i=='(':q+=1
        else:
            if q>0:q-=1
            else:ans+=1
    print(ans)

from collections import deque
import sys
def inp():
    return sys.stdin.readline().strip()
for _ in range(int(inp())):
    n=int(inp())
    s=inp()
    ct=0
    mn=0
    for i in s:
        if i=='(':
            ct+=1 
        else:
            ct-=1
        mn=min(ct,mn)
    print(abs(mn))