#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("avx,lzcnt,popcnt")
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;

namespace io {
char buf[1 << 21], *p, *q;
int getc() { return p == q && (q = (p = buf) + fread(buf, 1, 1 << 21, stdin), p == q) ? EOF : *p++; }
} // namespace io
using io::getc;
void readint(int &x) {
  x = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    ch = getc();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getc();
  }
}

const int N = 5e5 + 9;
int T, n, m, a[N];
bool g[2][N];
string s;
int mp[1000];

const int p1 = 998244353;
const int p2 = 1e9 + 7;
constexpr int power(int a, int b, int p) {
  int s = 1;
  for (; b; b >>= 1, a = (ll)a * a % p) {
    if (b & 1) s = (ll)s * a % p;
  }
  return s;
}

struct hsh {
  int x, y;
  bool operator<(const hsh &rhs) const { return x == rhs.x ? y < rhs.y : x < rhs.x; }
  bool operator==(const hsh &rhs) const { return x == rhs.x && y == rhs.y; }
  bool operator!=(const hsh &rhs) const { return x != rhs.x || y != rhs.y; }
  hsh operator+(const hsh &rhs) const {
    return {
        (x + rhs.x >= p1) ? (x + rhs.x - p1) : (x + rhs.x), //
        (y + rhs.y >= p2) ? (y + rhs.y - p2) : (y + rhs.y), //
    };
  }
  hsh operator-(const hsh &rhs) const {
    return {
        (x - rhs.x < 0) ? (x - rhs.x + p1) : (x - rhs.x), //
        (y - rhs.y < 0) ? (y - rhs.y + p2) : (y - rhs.y), //
    };
  }
  hsh operator*(const hsh &rhs) const {
    return {
        (int)((ll)x * rhs.x % p1), //
        (int)((ll)y * rhs.y % p2), //
    };
  }
} f[2][N], pw[N], ipw[N];
const hsh zeros = {0, 0};
const hsh ones = {1, 1};
const hsh base = {131131, 131131};
const hsh ibase = {power(base.x, p1 - 2, p1), power(base.y, p2 - 2, p2)};
inline hsh gethsh(int x) { return {x, x}; }

inline hsh peel(hsh x, int len, hsh low) { return (x - low) * ipw[len]; }
inline hsh extend(hsh x, int len, hsh high) { return x * pw[len] + high; }

struct interval {
  int l, r;
} b[N];

struct atom {
  hsh l, r, m;
  int ln, rn, mn, src;
  bool boom;
  atom() {
    ln = rn = mn = 0;
    l = r = m = zeros;
    src = -1;
    boom = false;
  }
};
struct segment {
  int l, r, mid;
  atom x;
} p[N << 2], q[N << 2];

hsh query_left(int u, int cnt) {
  if (!cnt) return zeros;
  if (p[u].l == p[u].r) {
    // assert(cnt == 1 && p[u].x.ln == 1);
    return p[u].x.l;
  }
  if (cnt == p[u].x.ln) {
    return p[u].x.l;
  }
  if (cnt <= p[u << 1].x.ln) {
    return query_left(u << 1, cnt);
  }
  cnt -= p[u << 1].x.ln;
  hsh tmp = query_left(u << 1 | 1, cnt + p[u].x.mn);
  tmp = peel(tmp, p[u].x.mn, p[u].x.m);
  tmp = extend(tmp, p[u << 1].x.ln, p[u << 1].x.l);
  return tmp;
}

hsh query_right(int u, int cnt) {
  if (!cnt) return zeros;
  // log("query_right u=%d[%d,%d] cnt=%d\n", u, p[u].l, p[u].r, cnt);
  if (p[u].l == p[u].r) {
    // assert(cnt == 1 && p[u].x.rn == 1);
    return p[u].x.r;
  }
  if (cnt == p[u].x.rn) {
    return p[u].x.r;
  }
  if (cnt <= p[u << 1 | 1].x.rn) {
    return query_right(u << 1 | 1, cnt);
  }
  cnt -= p[u << 1 | 1].x.rn;
  hsh tmp = query_right(u << 1, cnt + p[u].x.mn);
  tmp = peel(tmp, p[u].x.mn, p[u].x.m);
  tmp = extend(tmp, p[u << 1 | 1].x.rn, p[u << 1 | 1].x.r);
  return tmp;
}

atom merge(atom l, atom r) {
  atom x;
  if (l.boom || r.boom) {
    x.boom = true;
    return x;
  }
  x.mn = min(l.rn, r.ln);
  hsh lh = x.mn == l.rn ? l.r : query_right(l.src, x.mn);
  hsh rh = x.mn == r.ln ? r.l : query_left(r.src, x.mn);
  if (lh != rh) {
    x.boom = true;
    return x;
  }
  x.m = lh;
  x.ln = l.ln + r.ln - x.mn;
  x.rn = l.rn + r.rn - x.mn;
  x.l = extend(peel(r.l, x.mn, x.m), l.ln, l.l);
  x.r = extend(peel(l.r, x.mn, x.m), r.rn, r.r);
  return x;
}

void build(int u, int l, int r) {
  p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
  if (l == r) {
    p[u].x = atom();
    if (a[l] > 0) {
      p[u].x.rn = 1;
      p[u].x.r = gethsh(a[l]);
    } else {
      p[u].x.ln = 1;
      p[u].x.l = gethsh(-a[l]);
    }
    p[u].x.src = u;
    // log("u=%d l=%d r=%d >> ln=%d rn=%d mn=%d\n", u, p[u].l, p[u].r, p[u].x.ln, p[u].x.rn, p[u].x.mn);
    return;
  }
  build(u << 1, l, p[u].mid);
  build(u << 1 | 1, p[u].mid + 1, r);
  p[u].x = merge(p[u << 1].x, p[u << 1 | 1].x);
  // log("u=%d l=%d r=%d >> ln=%d rn=%d mn=%d boom=%d\n", u, p[u].l, p[u].r, p[u].x.ln, p[u].x.rn, p[u].x.mn, p[u].x.boom);
  p[u].x.src = u;
}

vector<atom> res;
void query(int u, int l, int r) {
  if (p[u].l == l && p[u].r == r) {
    res.push_back(p[u].x);
    return;
  }
  if (r <= p[u].mid) {
    query(u << 1, l, r);
  } else if (l > p[u].mid) {
    query(u << 1 | 1, l, r);
  } else {
    query(u << 1, l, p[u].mid);
    query(u << 1 | 1, p[u].mid + 1, r);
  }
}

struct stack_el {
  atom x;
  int n_use;
  hsh h_use;
};
vector<stack_el> stk;
pair<hsh, bool> query(int l, int r) {
  res.clear();
  stk.clear();
  query(1, l, r);
  // log("!!!!! query l=%d r=%d !!!!!\n", l, r);
  for (auto it : res) {
    // log("> src=%d boom=%d ln=%d rn=%d mn=%d\n", it.src, it.boom, it.ln,
    // it.rn, it.mn);
    if (it.boom) {
      // log("segment boomed!!\n");
      return make_pair(zeros, false);
    }
    int n_use = 0;
    hsh h_use = zeros;
    while (it.ln > n_use) {
      if (stk.empty()) {
        return make_pair(zeros, false);
      }
      int c = min(stk.back().x.rn - stk.back().n_use, it.ln - n_use);
      // log("!! c=%d\n", c);
      hsh lh_tmp = query_right(stk.back().x.src, stk.back().n_use + c);
      hsh lh = peel(lh_tmp, stk.back().n_use, stk.back().h_use);
      hsh rh_tmp = query_left(it.src, c + n_use);
      hsh rh = peel(rh_tmp, n_use, h_use);
      // log("lh={%d,%d} rh={%d,%d}\n", lh_tmp.x, lh_tmp.y, rh_tmp.x, rh_tmp.y);
      // log("lh={%d,%d} rh={%d,%d}\n", lh.x, lh.y, rh.x, rh.y);
      if (lh != rh) {
        return make_pair(zeros, false);
      }
      stk.back().n_use += c;
      stk.back().h_use = lh_tmp;
      n_use += c;
      h_use = rh_tmp;
      if (stk.back().n_use == stk.back().x.rn) {
        stk.pop_back();
      }
    }
    if (it.rn) {
      stk.push_back({it, 0, zeros});
    }
  }
  hsh res = zeros;
  for (auto it : stk) {
    int len = it.x.rn - it.n_use;
    hsh now = peel(it.x.r, it.n_use, it.h_use);
    res = extend(res, len, now);
  }
  return make_pair(res, true);
}

void reverse(int u, int dep) {
  // log("reverse %d %d\n", u, dep);
  const auto &it = p[u];
  int v = (1 << dep) * 3 - u - 1;
  auto &jt = q[v];
  jt.l = n - it.r + 1;
  jt.r = n - it.l + 1;
  jt.mid = n - it.mid; // ???? it.mid + 1 ????
  jt.x = it.x;
  jt.x.src = v;
  swap(jt.x.l, jt.x.r);
  swap(jt.x.ln, jt.x.rn);
  if (it.l == it.r) {
    return;
  }
  reverse(u << 1, dep + 1);
  reverse(u << 1 | 1, dep + 1);
}

void dfs(int u) {
  // log("p[%d] l=%d mid=%d r=%d\n", u, p[u].l, p[u].mid, p[u].r);
  if (p[u].l == p[u].r) {
    return;
  }
  dfs(u << 1);
  dfs(u << 1 | 1);
}

int main() {
#ifdef memset0
  freopen("B.in", "r", stdin);
  // freopen("B2.txt", "w", stderr);
#endif
  mp['('] = 1;
  mp[')'] = -1;
  mp['<'] = 2;
  mp['>'] = -2;
  mp['['] = 3;
  mp[']'] = -3;
  mp['{'] = 4;
  mp['}'] = -4;

  pw[0] = ipw[0] = ones;
  for (int i = 1; i < N; i++) {
    pw[i] = pw[i - 1] * base;
    ipw[i] = ipw[i - 1] * ibase;
  }

  readint(T);
  while (T--) {
    readint(n), readint(m);
    for (int i = 1; i <= n; i++) {
      a[i] = mp[(int)getc()];
    }
    for (int i = 1; i <= m; i++) {
      readint(b[i].l);
      readint(b[i].r);
    }

    for (int t = 0; t < 2; t++) {
      for (int i = 1; i <= n; i++) log("%d%c", a[i], " \n"[i == n]);
      if (t == 0) {
        build(1, 1, n);
      } else {
        reverse(1, 0);
        for (int i = 1; i < (n << 2); i++) {
          p[i] = q[i];
        }
      }
      dfs(1);
      for (int i = 1; i <= m; i++) {
        auto it = query(b[i].l, b[i].r);
        f[t][i] = it.first;
        g[t][i] = it.second;
        // log(">> t=%d i=%d[%d,%d] f={%d,%d} g=%d\n", t, i, b[i].l, b[i].r,
        //     f[t][i].x, f[t][i].y, g[t][i]);
      }

      reverse(a + 1, a + n + 1);
      for (int i = 1; i <= n; i++) {
        a[i] *= -1;
      }
      for (int i = 1; i <= m; i++) {
        b[i] = {n - b[i].r + 1, n - b[i].l + 1};
      }
    }

    int zero = 0;
    map<hsh, int> mp[2];
    set<hsh> val;
    for (int i = 1; i <= m; i++) {
      if (g[0][i] && g[1][i]) {
        zero++;
      } else if (g[0][i]) {
        mp[0][f[0][i]]++;
        val.insert(f[0][i]);
      } else if (g[1][i]) {
        mp[1][f[1][i]]++;
        val.insert(f[1][i]);
      }
    }
    int ans = zero >> 1;
    for (auto it : val) {
      ans += min(mp[0][it], mp[1][it]);
    }
    cout << ans << endl;
  }
}