/**
 *    author:  tourist
 *    created: 06.11.2022 20:54:05
**/
#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;
}