#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <typename T>

////////////////////////////////////////////
class fenwick                            //
{
    public:
    vector<T> fenw;

    int n;


   fenwick(int _n) : n(_n)
   {
        fenw.resize(n);
   }


    void modify(int x, T v)
    {

        while (x < n)
        {
            fenw[x] += v;
            x |= (x + 1);
        }
    }


  T get(int x)
  {

        T v{};

        while (x >= 0)
        {
            v += fenw[x];
            x = (x & (x + 1)) - 1;
        }

        return v;
   }

};

////////////////////////////////////////////
int main()                               //
{

  ios::sync_with_stdio(false);

  cin.tie(0);

  int tt;

  cin >> tt;

  while (tt--)
  {
        int n;
        cin >> n;
        string s;

        cin >> s;

        vector<int> a(n + 1);

        for (int i = 0; i < n; i++)   a[i + 1] = a[i] + (s[i] == '(' ? 1 : -1);

        int mn = *min_element(a.begin(), a.end());

    for (int i = 0; i <= n; i++)
    {
        a[i] -= mn;
        assert(0 <= a[i] && a[i] <= n);
    }

    long long ans = 0;

    fenwick<long long> f0(n + 1);
    fenwick<long long> f1(n + 1);

    for (int i = 0; i <= n; i++)
    {
        ans += f0.get(a[i]) * a[i] - f1.get(a[i]);
        f0.modify(a[i], +1);
        f1.modify(a[i], +a[i]);
    }

    vector<long long> pref(n + 2);

    for (int i = 0; i <= n; i++)  pref[i + 1] = pref[i] + a[i];

    vector<int> pr(n + 1);
    vector<int> ne(n + 1);

    for (int i = 0; i <= n; i++)
    {
        pr[i] = i - 1;
        ne[i] = i + 1;
    }

    vector<vector<int>> at(n + 1);

    for (int i = 0; i <= n; i++) at[a[i]].push_back(i);

    for (int val = n; val >= 0; val--)
    {
        for (int i : at[val])
        {

            int L = pr[i] + 1;
            int R = ne[i];
            long long cur = (pref[i] - pref[L]) - (long long) a[i] * (i - L);

            cur *= R - i;
            ans += cur;

            if (pr[i] != -1)    ne[pr[i]] = ne[i];

            if (ne[i] != n + 1) pr[ne[i]] = pr[i];

        }
    }

    cout << ans << '\n';

  }

  return 0;

}