#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

#define int int64_t

int norm(int x, int mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

struct InfArr {
    vector<int> val;
    vector<int> ind;
    int n;

    InfArr() {}

    int get_i_by_x(int x) {
        int rem = norm(x, n);
        int i = ind[rem];
        int k = (x - rem) / n;
        i += val.size() * k;
        return i;
    }

    int get_x_by_i(int i) {
        int rem = norm(o, val.size());
        int x = val[rem];
        int k = (i - rem) / (int)val.size();
        x += n * k;
        return x;
    }

    InfArr(string s) {
        n = s.size();
        ind.resize(n);
        for (int i = 0; i < n; ++i) {
            ind[i] = val.size();
            if (s[i] == ')') {
                val.push_back(i);
            }
        }
    }
};

const int MAXN = 1e5 + 100, MAXLN = 20;
int sp[MAXLN][MAXN], lg[MAXN];

const int INF = 1e9 + 100;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += (s[i] == '(');
    }
    if (cnt == 0 || cnt == n) {
        int q;
        cin >> q;
        while (q--) {
            int k, l, r;
            cin >> k >> l >> r;
            if (cnt == 0) {
                cout << "0\n";
            } else {
                cout << r - l + 1 << "\n";
            }
        }
        return;
    }
    InfArr arr1 = InfArr(s);
    string t = s;
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; ++i) {
        t[i] = '(' + ')' - t[i];
    }
    InfArr arr2 = InfArr(t);

    auto get_seg = [&](int x, int k) -> array<int, 2> {
        int id = arr1.get_i_by_x(x);
        id += k - 1;
        int r = arr1.get_x_by_i(id);
        id = arr2.get_i_by_x(n - x);
        id += k - 1;
        int l = n - arr2.get_x_by_i(id);
        return {l, r};
    };

    vector<int> bal(n, 0);
    for (int i = 1; i < n; ++i) {
        bal[i] = bal[i - 1];
        if (s[i - 1] == ')') {
            bal[i]--;
        } else {
            bal[i]++;
        }
    }
    int total = bal[n - 1];
    if (s[n - 1] == ')') {
        total--;
    } else {
        total++;
    }

    vector<int> pref(n + 1), suf(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = max(pref[i], bal[i]);
    }
    suf.back() = -INF;
    for (int i = n - 1; i >= 0; --i) {
        suf[i] = max(suf[i + 1], bal[i]);
    }

    for (int i = 0; i < n; ++i) {
        sp[0][i] = bal[i];
    }
    for (int lvl = 1; lvl < MAXLN; ++lvl) {
        for (int i = 0; i + (1 << lvl) <= n; ++i) {
            sp[lvl][i] = max(sp[lvl - 1][i], sp[lvl - 1][i + (1 << (lvl - 1))]);
        }
    }
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    auto get_sp = [&](int l, int r) {
        r++;
        int lvl = lg[r - l];
        return max(sp[lvl][l], sp[lvl][r - (1 << lvl)]);
    };

    auto get_max = [&](int l, int r) {
        int reml = norm(l, n), remr = norm(r, n);
        int kl = (l - reml) / n, kr = (r - remr) / n;
        if (kl == kr) {
            /// cerr << "here" << endl;
            int mx = get_sp(reml, remr);
            return mx + kl * total;
        }
        int mx = max(kl * total + suf[reml]
                   , kr * total + pref[remr + 1]);
        if (kr - kl > 1) {
            int all = suf[0];
            all += max(total * (kl + 1), total * (kr - 1));
            mx = max(mx, all);
        } 
        return mx;
    };

    auto get_bal = [&](int x) {
        int rem = norm(x, n);
        int k = (x - rem) / n;
        return bal[rem] + k * total;
    };

    auto count_op = [&](int x, int k) {
        auto res = get_seg(x, k);
        /**if (k == 2) {
            cerr << res[0] << " " << x << " " << res[1] << endl;
        }*/
        int mx = get_max(res[0], res[1]);
        /**if (k == 2) {
            cerr << mx << endl;
        }*/
        int cur = get_bal(x);
        /**if (k == 2) {
            cerr << cur << endl;
        }*/
        cur -= 2 * k - 1;
        return mx - cur;
    };

    auto get_val = [&](int x, int k) {
        int l = 0, r = k + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            int cnt = count_op(x, m);
            if (cnt <= k) {
                l = m;
            } else {
                r = m;
            }
        }
        /// cerr << x << " " << k << "->" << l << endl;
        return get_bal(x) - 2 * l;
    };

    int q;
    cin >> q;
    while (q--) {
        int k, l, r;
        cin >> k >> l >> r;
        ++r;
        if (k > n + 10) {
            int dif = k - (n + 10);
            k = n + 10;
            if (total > 0) {
                l += dif;
                r += dif;
            } else {
                l -= dif;
                r -= dif;
            }
        }
        int ans = get_val(r, k) - get_val(l, k);
        /// cerr << "!!!!" << endl;
        cout << (ans + r - l) / 2 << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

answer.code: In member function ‘int64_t InfArr::get_x_by_i(int64_t)’:
answer.code:34:24: error: ‘o’ was not declared in this scope
   34 |         int rem = norm(o, val.size());
      |                        ^