SPOJ BRCKTS2

#define ll long long
#include <bits/stdc++.h>
using namespace std;

/*
Ordered set usage:
order_of_key (k) : Number of items strictly smaller than k.
find_by_order(k) : K-th element in a set (counting from zero).
*/

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int OO = 1e9;
const double EPS = 1e-9;

int c[350000];

pair<pair<ll,ll>,ll> solve(int s, int e) {
    if(s+1 == e) {
        //cout << "at s = " << s << " e = " << e << " ret is " << 1 << " " << 1 << " " << 1 << "\n";
        return {{1,1},1};
    }
    ll h = 1;
    ll w = 2;
    ll area = 0;
    for(int i = s+1; i < e; i = c[i]+1) {
        pair<pair<ll,ll>,ll> ret = solve(i,c[i]);
        h = max(h,ret.first.first+1);
        w += ret.first.second;
        if(i > s+1) {
            w++;
        }
        area += ret.second;
    }
    //cout << "at s = " << s << " e = " << e << " ret is " << h << " " << w << " " << h*w-area << "\n";
    return {{h,w},h*w-area};
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--) {
        stack<int> stk;
        string s;
        cin >> s;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ')') {
                c[stk.top()] = i;
                stk.pop();
            }
            else {
                stk.push(i);
            }
        }
        ll ans = 0;
        for(int i = 0; i < s.size(); i = c[i]+1) {
            ans += solve(i,c[i]).second;
            //cout << "ans is " << ans << "\n";
        }
        cout << ans << "\n";
    }
    return 0;
}