#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>
#define x first
#define y second
using ll = long long;
using namespace std;
void solve();

const int P1=998244853,P2=1e9+9,B1=17,B2=37;
const int N=5e5+3;
int pw1[N],pw2[N];
map<char,int>W;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    W['(']=1;W[')']=-1;
    W['[']=2;W[']']=-2;
    W['{']=3;W['}']=-3;
    W['<']=4;W['>']=-4;
    int n=5e5;
    pw1[0]=pw2[0]=1;
    for(int i=1;i<=n;i++){
        pw1[i]=(ll)pw1[i-1]*B1%P1;
        pw2[i]=(ll)pw2[i-1]*B2%P2;
    }
	int t=1;
	cin>>t;
	while(t--)solve();
}
struct Hash{
    int a,b,n;
    void add(int w){
        ++n;
        a=((ll)a*B1+w)%P1;
        b=((ll)b*B2+w)%P2;
    }
    friend Hash operator-(const Hash &hx,const Hash &hy){
        Hash h;
        h.n=hx.n-hy.n;
        h.a=(hx.a-(ll)hy.a*pw1[h.n])%P1;
        h.b=(hx.b-(ll)hy.b*pw2[h.n])%P2;
        if(h.a<0)h.a+=P1;
        if(h.b<0)h.b+=P2;
        return h;
    }
    bool operator==(const Hash &h)const{
        return a==h.a&&b==h.b&&n==h.n;
    }
    bool operator!=(const Hash &h)const{
        return !(*this==h);
    }
    bool operator<(const Hash &h)const{
        if(n==h.n){
            if(a==h.a)return b<h.b;
            return a<h.a;
        }
        return n<h.n;
    }
};
struct node{
    int l,r;
    Hash u[2];
};
vector<node>ques;
int fa[N],dead[N];
Hash h[N];
void calc(vector<int> &_p,int o){
    vector<int>p{-5};
    for(auto c:_p)p.push_back(c);
    p.push_back(-5);
    vector<int>S;
    h[0]={0,0,0};
    S.push_back(0);
    for(int i=-1;auto c:p){
        ++i;
        if(i==0)continue;
        if(c>0){
            assert(S.size());
            fa[i]=S.back();
            h[i]=h[fa[i]];h[i].add(c);
            // cerr<<"* "<<i<<" "<<c<<" "<<h[i].a<<" "<<h[i].n<<endl;
            S.push_back(i);
        }
        else{
            assert(S.size());
            if(p[S.back()]==-c){
                dead[S.back()]=i;
                S.pop_back();
                assert(S.size());
                h[i]=h[S.back()];
            }
            else{
                while(S.size()){
                    dead[S.back()]=i;
                    S.pop_back();
                }
                S.push_back(i);
                h[i]={0,0,0};
            }
        }
    }
    int n=_p.size();
    for(auto &[_l,_r,u]:ques){
        int l=_l,r=_r;
        if(o)l=n-_r+1,r=n-_l+1;
        // cerr<<"^ "<<o<<" "<<l<<" "<<r<<" "<<fa[l]<<" "<<h[r].a<<" "<<h[fa[l]].a<<endl;
        if(p[l]<0||dead[fa[l]]<=r)u[o].n=-1;
        else u[o]=h[r]-h[fa[l]];
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    string s;cin>>s;
    vector<int>p;
    for(auto c:s){
        p.push_back(W[c]);
    }
    ques.clear();
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        ques.push_back({l,r});
    }
    calc(p,0);
    for(auto &c:p)c=-c;
    reverse(p.begin(),p.end());
    calc(p,1);

    // for(auto &[l,r,u]:ques){
    //     cerr<<"! "<<l<<" "<<r<<" "<<u[0].a<<" "<<u[0].n<<" "<<u[1].a<<" "<<u[1].n<<endl;
    // }
    map<Hash,int>C;
    int c0=0;
    for(auto &[l,r,u]:ques){
        if(u[0]==(Hash){0,0,0}){
            // assert((u[1]==(Hash){0,0,0}));
            ++c0;
        }
        else if(u[0].n!=-1){
            // assert(u[1].n==-1);
            C[u[0]]++;
        }
    }
    int ans=c0/2;
    for(auto &[l,r,u]:ques){
        if((u[0]!=(Hash){0,0,0})&&u[1].n!=-1){
            // assert(u[0].n==-1);
            if(C[u[1]]){
                --C[u[1]];
                ++ans;
            }
        }
    }
    cout<<ans<<endl;
}