#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
#define rep2(i,l,r) for(ll i=ll(l); i<ll(r); i++)

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

mt19937 engine(42);

vector<pair<int, int>> Bipartite_Mathing(int n, int m, vector<pair<int, int>> edges) {
  shuffle(edges.begin(), edges.end(), engine);
  vi G(edges.size()), L(n, -1), R(m, -1), deg(n + 1), a, p, q(n);
  for (auto &[x, y] : edges) deg[x]++;
  rep(i, n) deg[i + 1] += deg[i];
  for (auto &[x, y] : edges) G[--deg[x]] = y;
  while (true) {
    a.assign(n, -1), p.assign(n, -1);
    int t = 0;
    rep(i, n) {
      if (L[i] == -1) {
        q[t++] = a[i] = p[i] = i;
      }
    }
    bool match = false;
    rep(i, t) {
      int x = q[i];
      if (L[a[x]] != -1) continue;
      rep2(j, deg[x], deg[x + 1]) {
        int y = G[j];
        if (R[y] == -1) {
          while (y != -1) {
            R[y] = x;
            swap(L[x], y);
            x = p[x];
          }
          match = true;
          break;
        }
        if (p[R[y]] == -1) {
          q[t++] = y = R[y];
          p[y] = x;
          a[y] = a[x];
        }
      }
    }
    if (!match) break;
  }
  vector<pair<int, int>> res;
  rep(i, L.size()) {
    if (L[i] != -1) res.push_back({i, L[i]});
  }
  return res;
}

void solve() {
  ll N, M; cin >> N >> M;
  vector< pair<int, int> > edge(M);
  for (ll i = 0; i < M; ++i) {
    ll u, v; cin >> u >> v;
    u--, v--;
    edge[i] = {u, v};
  }

  vector<pair<int, int>> match = Bipartite_Mathing(N, N, edge);
  set< pair<int, int> > st;
  for (auto [u, v] : match) st.insert({u, v});
  
  vector<pair<int, int>> non;
  for (auto [u, v] : edge) {
    if (st.find({u, v}) == st.end()) {
      non.push_back({u, v});
    }
  }

  vector<ll> Sok(N, 0), Sng(N, 0), Tok(N, 0), Tng(N, 0);
  for (auto [u, v] : non) {
    Tng[v] = 1;
    Sng[u] = 1;
  }
  vector<int> isS(N, 0), isT(N, 0);
  for (auto [u, v] : match) {
    if (Tng[v]) Sok[u] = 1;
    if (Sng[u]) Tok[v] = 1;

    isS[u] = isT[v] = 1;
  }

  // for (ll u = 0; u < N; ++u) {
  //   cout << u << " " << Sok[u] << " " << isS[u] << endl;
  // }

  {
    ll s = 0, t = 0;
    for (ll i = 0; i < N; ++i) {
      if (isS[i] == 0 || Sok[i] == 1) {
        s++;
      }
    }
    for (ll i = 0; i < N; ++i) {
      if (isT[i] == 0 || Tok[i] == 1) {
        t++;
      }
    }
    ll res = s * t;
    cout << res << endl;
  }

  return;
}

int main() {
  ll T; cin >> T;
  while (T--) {
    solve();
  }

  return 0;
}