#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);
    vector<int> ck[2];
    for (int i = 1; i <= 2 * n; ++i) {
        if (vis[i])
            continue;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        int cnt[2] = {0, 0};
        cnt[i > n] = 1;
        while (!q.empty()) {
            auto x = q.front();
            q.pop();

            for (const auto &y : e[x]) {
                if (vis[y])
                    continue;
                vis[y] = 1;
                cnt[y > n]++;
                q.push(y);
            }
        }

        if (cnt[0] > cnt[1])
            ck[0].push_back(cnt[0]);
        else if (cnt[0] < cnt[1])
            ck[1].push_back(cnt[1]);
    }

    ll sum = 0;
    for (const auto &c : ck[0])
        sum += c;
    ll ans = 0;
    for (const auto &c : ck[1])
        ans += sum * c;

    cout << ans << '\n';
}

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

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