#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

long mod1 = 740157631;
long mod2 = 521657681;
long base = 239239;

vector<long> pow1 = {1}, pow2 = {1};

typedef pair<long, long> stringhash;

stringhash add(stringhash a, int x) {
    return {(a.first * base + x) % mod1, (a.second * base + x) % mod2};
}

stringhash mult(stringhash a, int x) {
    while (x >= (int)pow1.size()) {
        pow1.push_back((pow1.back() * base) % mod1);
        pow2.push_back((pow2.back() * base) % mod2);
    }
    return {(a.first * pow1[x]) % mod1, (a.second * pow2[x]) % mod2};
}

stringhash sub(stringhash a, stringhash b) {
    return {(a.first - b.first + mod1) % mod1, (a.second - b.second + mod2) % mod2};
}


struct test {
    int n, m;
    vector<int> s;
    vector<int> l, r;
    vector<stringhash> res1, res2;

    void calc() {
        vector<int> st = {-1};
        vector<int> stc = {0};
        vector<stringhash> sth = {{0, 0}};
        vector<vector<int>> ll(n);
        for (int i = 0; i < m; i++) {
            ll[r[i] - 1].push_back(i);
        }
        for (int i = 0; i < n; i++) {
            if ((st.back() != -1) && (s[i] & 1) && (s[st.back()] == s[i] - 1)) {
                st.pop_back();
                stc.pop_back();
                sth.pop_back();
            } else {
                st.push_back(i);
                stc.push_back(stc.back() + (s[i] & 1));
                sth.push_back(add(sth.back(), s[i] + 1));
            }
            for (int j: ll[i]) {
                int ll = l[j];
                int x = lower_bound(st.begin(), st.end(), ll) - st.begin();
                if (stc[x - 1] != stc.back()) {
                    if (stc.back() - stc[x - 1] != (int)sth.size() - x) {
                        res1[j] = {LLONG_MAX, LLONG_MAX};
                    }
                } else {
                    res1[j] = sub(sth.back(), mult(sth[x - 1], (int)sth.size() - x));
                }
            }
        }
    }

    void solve() {
        cin >> n >> m;
        string ss;
        cin >> ss;
        s.resize(n);
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < 8; i++) {
                if (ss[j] == "()[]{}<>"[i]) {
                    s[j] = i;
                    break;
                }
            }
        }

        l.resize(m);
        r.resize(m);
        res1.resize(m);
        res2.resize(m);
        for (int i = 0; i < m; i++) {
            cin >> l[i] >> r[i];
            l[i]--;
        }
        calc();
        for (int &c: s) {
            c = c ^ 1;
        }
        reverse(s.begin(), s.end());
        for (int i = 0; i < m; i++) {
            l[i] = n - l[i];
            r[i] = n - r[i];
            swap(l[i], r[i]);
        }
        swap(res1, res2);
        calc();
        stringhash zero = {0, 0};
        map<stringhash, int> mp;
        int nz = 0;
        for (int i = 0; i < m; i++) {
            if (res1[i] == zero && res2[i] == zero) {
                nz++;
            }
        }
        for (int i = 0; i < m; i++) {
            if (res1[i] != zero && res2[i] != zero) {
                continue;
            }
            if (res1[i] != zero) {
                mp[res1[i]]++;
            }
        }
        long res = nz / 2;
        for (int i = 0; i < m; i++) {
            if (res1[i] != zero && res2[i] != zero) {
                continue;
            }
            if (res2[i] != zero) {
                if (mp[res2[i]] > 0) {
                    mp[res2[i]]--;
                    res++;
                }
            }
        }
        cout << res << "\n";
    }
};

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }

    return 0;
}