类似于一个补一个“最近匹配”的括号。
因为需要括号的举例最短，所以贪心补），如果能补），优先补）。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include "bits/stdc++.h"
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fios ofstream("text.txt");cout.rdbuf(out.rdbuf())
#define INF 0x3f3f3f3f
#define MINF 2147483637
#define eps 1e-6
#define PI acos(-1)
#define lowbit(x) (x & (-x))
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 200010;

int n;
string str;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        cin >> str;

        int d = 0;
        str[0] = '(';
        for(int i = 0; i < str.size(); i++)
        {
            if(str[i] == '(') d++;
            if(str[i] == ')') d--;

            if(str[i] == '_')
            {
                if(d > 0)
                {
                    str[i] = ')';
                    d--;
                }
                else
                {
                    str[i] = '(';
                    d++;
                }
            }
         }

         //cout << str << endl;

         int res = 0, cnt = 0;
         for(int i = 0; i < str.size(); i++)
         {
             res += cnt;
             if(str[i] == '(') cnt++;
             else cnt--;
         }

         cout << res << endl;
    }

    return 0;
}