#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const ULL mod = (1ULL << 61) - 1;
const ULL base = 124123421431;
const int maxn = 5e5 + 5;
ULL power[maxn];

ULL add(ULL a, ULL b){
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

ULL mul(ULL a, ULL b){
    __int128_t c = __int128_t(a) * b;
    return add(c & mod, c >> 61);
}

ULL query(vector<ULL> &hsh, int l, int r){
    return add(hsh[r], mod - mul(hsh[l - 1], power[r - l + 1]));
}

int p[maxn];
void init(int n){
    for(int i = 0; i <= n; i++) p[i] = i;
}

int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    if (x != y) p[x] = y;
}

const int INF = 1e9;

int lowbit(int x){
    return x & -x;
}

namespace BIT_MAX{

int tr[maxn];
int n;

void init(int _n){
    n = _n;
    for(int i = 1; i <= n; i++) tr[i] = -INF;
}

void modify(int x, int v){
    while(x <= n){
        tr[x] = max(tr[x], v);
        x += lowbit(x);
    }
}

int query(int x){
    int ans = -INF;
    while(x){
        ans = max(ans, tr[x]);
        x -= lowbit(x);
    }
    return ans;
}

}

namespace BIT_MIN{

int tr[maxn];
int n;

void init(int _n){
    n = _n;
    for(int i = 1; i <= n; i++) tr[i] = INF;
}

void modify(int x, int v){
    while(x){
        tr[x] = min(tr[x], v);
        x -= lowbit(x);
    }
}

int query(int x){
    int ans = INF;
    while(x <= n){
        ans = min(ans, tr[x]);
        x += lowbit(x);
    }
    return ans;
}

}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    power[0] = 1;
    for(int i = 1; i < maxn; i++){
        power[i] = mul(power[i - 1], base);
    }

    int val[256]{}, type[256]{}, rev[256];
    val['('] = val['{'] = val['['] = val['<'] = 1;
    val[')'] = val['}'] = val[']'] = val['>'] = -1;
    type['('] = type[')'] = 0;
    type['{'] = type['}'] = 1;
    type['['] = type[']'] = 2;
    type['<'] = type['>'] = 3;
    rev[')'] = '(';
    rev['}'] = '{';
    rev[']'] = '[';
    rev['>'] = '<';

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;
        s = " " + s;
        vector<int> pre(n + 1);
        for(int i = 1; i <= n; i++){
            pre[i] = pre[i - 1] + val[s[i]];
        }
        init(n);
        {
            vector<ULL> hsh;
            vector<int> stk;
            for(int i = 1; i <= n; i++){
                if (val[s[i]] == 1){
                    stk.push_back(i);
                }
                else{
                    if (!stk.empty() and type[s[stk.back()]] == type[s[i]]){
                        merge(i, stk.back() - 1);
                        stk.pop_back();
                    }
                    else{
                        stk.clear();
                    }
                }
            }
        }
        vector<vector<int> > pos[2];
        pos[0].resize(n + 1);
        pos[1].resize(n + 1);
        int ans = 0;
        for(int i = 0; i < m; i++){
            int l, r;
            cin >> l >> r;
            if (pre[r] - pre[l - 1] == 0){
                if (find(l - 1) == find(r)){
                    ans += 1;
                }
            }
            else{
                if (pre[r] - pre[l - 1] > 0){
                    pos[0][r].push_back(l);
                }
                else{
                    pos[1][l].push_back(r);
                }
            }
        } 
        ans /= 2;
        map<ULL, int> mp;
        {
            vector<ULL> hsh{0};
            vector<int> stk;
            int bad = 0;
            BIT_MAX::init(n);
            for(int i = 1; i <= n; i++){
                if (val[s[i]] == 1){
                    stk.push_back(i);
                    hsh.push_back(add(mul(hsh.back(), base), s[i]));
                }
                else{
                    if (!stk.empty() and type[s[stk.back()]] == type[s[i]]){
                        BIT_MAX::modify(stk.back(), i);
                        stk.pop_back();
                        hsh.pop_back();
                    }
                    else{
                        bad = i;
                        stk.clear();
                        hsh = {0};
                    }
                }
                for(auto l : pos[0][i]){
                    if (bad >= l) continue;
                    if (BIT_MAX::query(l - 1) >= l) continue;
                    int pos = lower_bound(stk.begin(), stk.end(), l) - stk.begin() + 1;
                    mp[query(hsh, pos, stk.size())] += 1;
                }
            }
        }
        {
            vector<ULL> hsh{0};
            vector<int> stk;
            int bad = n + 1;
            BIT_MIN::init(n);
            for(int i = n; i >= 1; i--){
                if (val[s[i]] == -1){
                    stk.push_back(i);
                    hsh.push_back(add(mul(hsh.back(), base), rev[s[i]]));
                }
                else{
                    if (!stk.empty() and type[s[stk.back()]] == type[s[i]]){
                        BIT_MIN::modify(stk.back(), i);
                        stk.pop_back();
                        hsh.pop_back();
                    }
                    else{
                        bad = i;
                        stk.clear();
                        hsh = {0};
                    }
                }
                for(auto r : pos[1][i]){
                    if (bad <= r) continue;
                    if (BIT_MIN::query(r + 1) <= r) continue;
                    int pos;
                    {
                        int L = 0, R = stk.size() - 1;
                        while(L < R){
                            int mid = (L + R) / 2;
                            if (stk[mid] <= r) R = mid;
                            else L = mid + 1;
                        }
                        pos = R + 1;
                    }
                    ULL h = query(hsh, pos, stk.size());
                    if (mp.contains(h)){
                        ans += 1;
                        if (--mp[h] == 0){
                            mp.erase(h);
                        }
                    }
                }
            }
        }
        cout << ans << '\n';
    }

}