#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int M = 101010;

int n;
vector<int> g[M];

int par[M], ln[M], dn;
bool cyc[M];
void dfs(int p, int v) {
    ln[v] = ++dn;
    for (int x : g[v]) {
        if (p == x) continue;
        if (!ln[x]) {
            par[x] = v;
            dfs(v, x);
        }
        else if (ln[x] < ln[v]) {
            for (int y = v; y != x; y = par[y]) 
                cyc[y] = 1;
            cyc[x] = 1;
        }
    }
}

int dp[M];
void dfs2(int p, int v) {
    dp[v] = 0;
    for (int x : g[v]) if (p != x && !cyc[x]) {
        dfs2(v, x);
        dp[v] += dp[x];
    }
    if (p != v)
        dp[v] = max(dp[v], 1);
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    int t; cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(0, 1);

        int ans = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (cyc[i]) {
                dfs2(i, i);
                if (dp[i] != 0)
                    ans += dp[i];
                else    
                    ++cnt;
            }
        }
        cout << max(3, ans + min(2, cnt)) << '\n';

        dn = 0;
        for (int i = 1; i <= n; i++) {
            g[i].clear();
            par[i] = 0;
            cyc[i] = 0;
            ln[i] = 0;
            dp[i] = 0;
        }
    }
}