#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define x first
#define y second
#define Time (double)clock()/CLOCKS_PER_SEC
#define munq(a) sort(all(a)); a.resize(unique(all(a))-a.begin())
#define sz(a) ((int)a.size())
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
mt19937 rnd;
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)
double pi=acos(-1);
const int L = 20;
vector <int> inv(const vector <int> &p) {
    vector <int> q(L);
    for (int i = 0; i < L; ++i) {
        q[p[i]]=i;
    }
    return q;
}
vector <int> operator * (const vector <int> &p, const vector <int> &q) {
    vector <int> ans(L);
    for (int i = 0; i < L; ++i) {
        ans[i] = p[q[i]];
    }
    return ans;
}

template<typename T, typename U>
struct SegmentTree {
  int h, n;
  T neutral;
  U unite;
  vector<T> data;

  template<typename I>
  SegmentTree(int sz, T neutral, U unite, I init) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n) {
    for (int i = 0; i < sz; ++i) data[i + n] = init(i);
    for (int i = n - 1; i > 0; --i) data[i] = unite(data[2 * i], data[2 * i + 1]);
  }

  SegmentTree(int sz, T neutral, U unite) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n, neutral) {}

  void set(int i, T x) {
    data[i += n] = x;
    for (i /= 2; i > 0; i /= 2) data[i] = unite(data[2 * i], data[2 * i + 1]);
  }

  T get(int l, int r) {
    T leftRes = neutral, rightRes = neutral;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) leftRes = unite(leftRes, data[l++]);
      if (r & 1) rightRes = unite(data[--r], rightRes);
    }
    return unite(leftRes, rightRes);
  }
  int left(int i) {
    int lvl = __lg(i);
    return (i & ((1 << lvl) - 1)) * (1 << (h - lvl));
  }
  int right(int i) {
    int lvl = __lg(i);
    return ((i & ((1 << lvl) - 1)) + 1) * (1 << (h - lvl));
  }

  // l \in [0; n) && ok(get(l, l), l);
  // returns last r: ok(get(l, r), r)
  template<typename C>
  int lastTrue(int l, C ok) {
    T cur = neutral;
    l += n;
    do {
      l >>= __builtin_ctz(l);
      T with1 = unite(cur, data[l]);
      if (ok(with1, right(l))) {
        cur = with1;
        ++l;
      } else {
        while (l < n) {
          T with2 = unite(cur, data[2 * l]);
          if (ok(with2, right(2 * l))) {
            cur = with2;
            l = 2 * l + 1;
          } else {
            l = 2 * l;
          }
        }
        return l - n;
      }
    } while (l & (l - 1));
    return n;
  }

  // r \in [0; n) && ok(get(r, r), r);
  // returns first l: ok(get(l, r), l)
  template<typename C>
  int firstTrue(int r, C ok) {
    T cur = neutral;
    r += n;
    while (r & (r - 1)) {
      r >>= __builtin_ctz(r);
      T with1 = unite(data[--r], cur);
      if (ok(with1, left(r))) {
        cur = with1;
      } else {
        while (r < n) {
          T with2 = unite(data[2 * r + 1], cur);
          if (ok(with2, left(2 * r + 1))) {
            cur = with2;
            r = 2 * r;
          } else {
            r = 2 * r + 1;
          }
        }
        return r - n + 1;
      }
    }
    return 0;
  }
};

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;

    string u = "()[]{}<>";
    auto type = [&] (char c) {
        for (int i = 0; i < 8; ++i) {
            if (c == u[i]) {
                return i;
            }
        }
        assert(0);
    };

    mt19937 rnd(2007);

    vector <vector <int> > h(u.size());
    for (int i = 0; i < 4; ++i) {
        h[i * 2].assign(L, 0);
        iota(all(h[i * 2]), 0);
        shuffle(all(h[i * 2]), rnd);
        h[(i * 2) + 1] = inv(h[i * 2]);
    }



    while (t--) {
        int n, m; cin >> n >> m;
        string s;
        cin >> s;
        vector <vector <int> > pre(n + 1);
        pre.front().assign(L, 0);
        iota(all(pre.front()), 0);

        for (int i = 0; i < n; ++i) {
            pre[i + 1] = pre[i] * h[type(s[i])];
        }

        vector <vector <int> > b(4, vector <int> (n + 1));
        for (int i = 0; i < n; ++i) {

            for (int t = 0; t < 4; ++t) {
                b[t][i + 1] = b[t][i];
            }

            int t = type(s[i]);

            if (t%2==0) {
                b[t/2][i + 1]++;
            }
            else {
                b[t/2][i + 1]--;
            }


        }

        debug("now");

        map <pair <vector <int>, vector <int> > , vector <pair <int, int > > > d;
        for (int i = 0; i < m; ++i) {
            int l, r; cin >> l >> r;
            l--;

            vector <int> nb(4);
            for (int t = 0; t < 4; ++t) {
                nb[t] = b[t][r]-b[t][l];
            }

            vector <int> p = inv(pre[l]) * pre[r];

            d[{nb, p}].push_back({l,r});

        }

        debug("ok");
        auto calc = [](int x, int y) { return min(x, y); };
        vector <SegmentTree<int, decltype(calc)> > segtree(4, SegmentTree<int, decltype(calc)> (n + 1, (int)1e9, calc));

        for (int t = 0; t < 4; ++t) {
            for (int i = 0; i <= n; ++i) {
                segtree[t].set(i, b[t][i]);
            }
        }


        auto check = [&] (int l, int r) {
                                bool ok = true;
                    for (int t = 0; t < 4; ++t) {
                        ok &= b[t][l] == segtree[t].get(l, r+1);
                    }
                    return ok;
        };

        auto check2 = [&] (int l, int r) {
                                bool ok = true;
                    for (int t = 0; t < 4; ++t) {
                        ok &= b[t][r] == segtree[t].get(l, r+1);
                    }
                    return ok;
        };

        debug("here");

        vector <int> go(n, n);
        vector <int> stack;
        for (int i = 0; i < n; ++i) {
            if (type(s[i])%2==0) {
                stack.push_back(i);
            }
            else {
                if (!stack.empty()) {
                    int j = stack.back();

                    if (type(s[j])/2 != type(s[i])/2) {
                        go[j] = i;
                    }

                    stack.pop_back();
                }
            }
        }

        SegmentTree sg(n, (int)1e9,  [](int x, int y) { return min(x, y); });
        for (int i = 0; i < n; ++i) {
            sg.set(i, go[i]);
        }

        int ans = 0;
        for (auto e : d) {
            auto [nb, p] = e.first;
            bool no = true;
            for (int i = 0; i < 4; ++i) {
                no &= nb[i]==0;
            }
            if (no) {
                int k  =0;
                for (auto [l, r] : e.second) {
                    k += check(l, r) && (sg.get(l, r) >= r);
                }
                ans += k/2;
            }
            else {

                bool pos = true;
                for (int t = 0; t < 4; ++t) {
                    pos &= nb[t] >= 0;
                }

                if (pos) {
                    int a = 0;
                    for (auto [l, r] : e.second) {
                        a += check(l, r) && (sg.get(l, r) >= r);
                    }


                    auto nb1 = nb;
                    for (int &e : nb1) {
                        e = -e;
                    }
                    auto q = inv(p);

                    int c = 0;
                    for (auto [l, r] : d[make_pair(nb1, q)]) {
                        c += check2(l, r) && (sg.get(l, r) >= r);
                    }
                    ans += min(a, c);
                }


            }
        }
        debug("ans");
        debug(ans);
        cout << ans << '\n';
    }
    return 0;
}