#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>;

mt19937 engine;

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;
}

ll solve(int n,vector<pair<int,int>> &E){
    vector<pair<int,int>> ans=Bipartite_Mathing(n,n,E);

    vector<vector<int>> GA(n),GB(n);
    for(auto [a,b]:E){
        GA[a].push_back(b);
        GB[b].push_back(a);
    }

    vector<int> A(n,-1),B(n,-1);
    for(auto [a,b]:ans){
        A[a]=b;
        B[b]=a;
    }
    vector<bool> seenA(n,false),seenB(n,false);
    queue<int> Q;
    ll an=1;

    for(int i=0;i<n;i++){
        if(A[i]==-1)Q.push(i);
    }
    
    int cnt=0;
    while(!Q.empty()){
        int p=Q.front();
        Q.pop();
        if(seenA[p])continue;
        seenA[p]=1;
        cnt++;
        for(auto b:GA[p]){
            if(B[b]>=0&&!seenA[B[b]]){
                Q.push(B[b]);
            }
        }
    }
    an*=cnt;
    // cout<<cnt<<" ";

    for(int i=0;i<n;i++){
        if(B[i]==-1)Q.push(i);
    }
    
    cnt=0;
    while(!Q.empty()){
        int p=Q.front();
        Q.pop();
        if(seenB[p])continue;
        seenB[p]=1;
        cnt++;
        for(auto a:GB[p]){
            if(A[a]>=0&&!seenB[A[a]]){
                Q.push(A[a]);
            }
        }
    }
    an*=cnt;
    // cout<<cnt<<endl;
    cout<<an<<endl;
    return 0;
}


int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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