#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define range(x) (x).begin(), (x).end()
const int dir[][2] = {1, 0, -1, 0, 0, 1, 0, -1};

void solve()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> e(2 * n + 5);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(n + v);
        e[n + v].push_back(u);
    }

    vector<int> vis(2 * n + 5);
    ll sum[2] = {0};

    for (int i = 1; i <= 2 * n; ++i) {
        if (vis[i])
            continue;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        vector<int> use;
        int cnt[2] = {0, 0};
        cnt[i > n] = 1;
        while (!q.empty()) {
            auto x = q.front();
            q.pop();
            use.push_back(x);
            for (const auto &y : e[x]) {
                if (vis[y])
                    continue;
                vis[y] = 1;
                cnt[y > n]++;
                q.push(y);
            }
        }

        if (cnt[0] > cnt[1]) {
            map<int, set<int>> deg;
            for (const auto &c : use)
                if (c > n) {
                    for (const auto &y : e[c])
                        deg[c].insert(y);
                    if (deg[c].size() == 1)
                        q.push(c);
                }
            int sz = cnt[0];

            while (!q.empty()) {
                auto x = q.front();
                q.pop();
                assert(deg[x].size());
                int now = *deg[x].begin();
                sz--;
                for (const auto &y : e[now]) {
                    assert(deg[y].size());
                    deg[y].erase(now);
                    if (deg[y].size() == 1)
                        q.push(y);
                }
            }
            assert(sz > 0);
            sum[0] += sz;
        }
        else if (cnt[0] < cnt[1]) {
            map<int, set<int>> deg;
            for (const auto &c : use)
                if (c <= n) {
                    for (const auto &y : e[c])
                        deg[c].insert(y);
                    if (deg[c].size() == 1)
                        q.push(c);
                }

            int sz = cnt[1];
            while (!q.empty()) {
                auto x = q.front();
                q.pop();
                assert(deg[x].size());
                int now = *deg[x].begin();
                sz--;
                for (const auto &y : e[now]) {
                    assert(deg[y].size());

                    deg[y].erase(now);
                    if (deg[y].size() == 1)
                        q.push(y);
                }
            }
            assert(sz > 0);
            sum[1] += sz;
        }
    }

    cout << sum[0] * sum[1] << '\n';
}

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

    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}