#include <bits/stdc++.h>

const int MAXN = 5.501E5;
struct SEG {
  struct Node {
    int min, max;
    Node() {}
    Node(int _min, int _max) : min(_min), max(_max) {}
    Node friend operator + (const Node& x, const Node& y) {
      return Node(std::min(x.min, y.min), std::max(x.max, y.max));
    }
  };

  std::vector <Node> seg;
  SEG() {}
  inline void init(int n) {
    seg = std::vector <Node> (n << 2, Node());
  }

  void Ins(int o, int l, int r, int p, int v, int op) {
    if (l == r) {
      if (op) seg[o].min = v;
      else seg[o].max = v;
      return ;
    }

    int mid = l + r >> 1;
    if (p <= mid) Ins(o << 1, l, mid, p, v, op);
    else Ins(o << 1 | 1, mid + 1, r, p, v, op);
    seg[o] = seg[o << 1] + seg[o << 1 | 1];
  }

  Node query(int o, int l, int r, int x, int y) {
    if (x <= l && y >= r) return seg[o];
    int mid = l + r >> 1;
    Node res = Node();
    if (x <= mid) res = query(o << 1, l, mid, x, y);
    if (y > mid) res = res + query(o << 1 | 1, mid + 1, r, x, y);
    return res;
  }
} tree;

char S[MAXN];
int stackLim[MAXN], stackBracket[MAXN], toNum[255], limL[MAXN], limR[MAXN];
int N, M, topB, topLim;

const char toChar[] = {'(', ')', '[', ']', '{', '}', '<', '>'};
const int Base = 233;
unsigned long long Hash[MAXN], pw[MAXN];

std::vector <int> segmentL[MAXN], segmentR[MAXN];
std::unordered_map <unsigned long long, int> mp;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  toNum['('] = 0, toNum[')'] = 1, toNum['['] = 2, toNum[']'] = 3, toNum['{'] = 4, toNum['}'] = 5, toNum['<'] = 6, toNum['>'] = 7;
  for (int i = *pw = 1; i < MAXN; ++i) 
    pw[i] = pw[i - 1] * Base;

  int testCase = 1;
  std::cin >> testCase;
  while (testCase--) {
    std::cin >> N >> M >> S;
    mp.clear();
    for (int i = N; i; --i)
      S[i] = S[i - 1], segmentL[i].clear(), segmentR[i].clear();
    
    for (int i = 1, l, r; i <= M; ++i) {
      std::cin >> l >> r;
      segmentL[r].push_back(l);
      segmentR[l].push_back(r);
    }

    topB = topLim = 0;
    for (int i = 1; i <= N; ++i) {
      if (toNum[S[i]] & 1) {
        if (topB && toNum[S[stackBracket[topB]]] == (toNum[S[i]] ^ 1)) {
          limL[i] = stackBracket[topB--];
        } else topB = limL[i] = 0;
      } else {
        stackBracket[++topB] = i, limL[i] = 1e9;
        Hash[topB] = Hash[topB - 1] * Base + S[i];
      }

      while (topLim && limL[i] <= limL[stackLim[topLim]]) --topLim;
      stackLim[++topLim] = i;

      for (int l : segmentL[i]) {
       int p = std::lower_bound(stackLim + 1, stackLim + 1 + topLim, l) - stackLim;
       if (limL[stackLim[p]] >= l) {
          p = std::lower_bound(stackBracket + 1, stackBracket + 1 + topB, l) - stackBracket;
          auto nowH = Hash[topB] - Hash[p - 1] * pw[topB - p + 1];
          ++mp[nowH];
          // std::cout << "HaL : ";
          // std::cout << l << " " << i << " " << nowH << '\n';
       }
      }
    }
    
    topB = topLim = 0;
    int ans = 0;
    for (int i = N; i; --i) {
      if ((toNum[S[i]] & 1) == 0) {
        if (topB && toNum[S[stackBracket[topB]]] == (toNum[S[i]] ^ 1)) {
          limR[i] = stackBracket[topB--];
        } else topB = 0, limR[i] = 1e9;
      } else {
        stackBracket[++topB] = i, limR[i] = 0;
        Hash[topB] = Hash[topB - 1] * Base + (toChar[toNum[S[i]] ^ 1]);
      }

      while (topLim && limR[i] >= limR[stackLim[topLim]]) --topLim;
      stackLim[++topLim] = i;

      for (int r : segmentR[i]) {
       int p = std::lower_bound(stackLim + 1, stackLim + 1 + topLim, r, std::greater <int> ()) - stackLim;
       if (limR[stackLim[p]] <= r) {
          p = std::lower_bound(stackBracket + 1, stackBracket + 1 + topB, r, std::greater <int> ()) - stackBracket;
          auto nowH = Hash[topB] - Hash[p - 1] * pw[topB - p + 1];
          if (nowH != 0 && mp[nowH] > 0)
            ++ans, --mp[nowH];
          // std::cout << "Ha : ";
          // std::cout << i << " " << r << " " << nowH << '\n';
       }
      }
    }

    ans += mp[0] / 2;
    std::cout << ans << '\n';
  }

  return 0;
}