#!/usr/bin/python
import sys

t = int(sys.stdin.readline())

for case in range(t):
    s = sys.stdin.readline()
    s = sys.stdin.readline()
    z, n = [], len(s)-1
    if n % 2 == 1:
        raise Exception("N is odd")

    res = 0
    for i in range(n):
        if s[i] == '(':
            z.append([i, 1, 0])
        else:
            if len(z) == 0:
                raise Exception("Bracket sequence is not correct")
            o = z[-1]
            z.pop()
            o[0] = i - o[0]
            if len(z) % 2 == 0:
                res += o[0] * o[1] + o[2]

            if len(z) > 0:
                z[-1][2] -= o[0] * o[1]
                z[-1][1] = max(z[-1][1], o[1] + 1)
    print res
    if len(z) > 0:
        raise Exception("Bracket sequence is not correct")