#include <bits/stdc++.h>
using namespace std;
#define M 100010
vector<int> G[M];
int d[M];
int vis[M];
int st[M], tot;
vector<int> cir;
bool flag;
void dfs(int x, int fa) {
    // cout << "now  " << x << " " << fa << endl;
    vis[x] = 1;
    st[++ tot] = x;    
    // int cc = x;
    for(int i = 0; i < G[x].size(); ++ i) {
        int v = G[x][i];
        if(v == fa) continue;
        if(vis[v] == 0) {
            dfs(v, x);
            if(flag) return;
        }
        else {
            flag = 1;
            for(int j = tot; j; -- j) {
                // cout << j << " " << "st   " << st[j] << " " << v << endl;
                cir.push_back(st[j]);
                if(st[j] == v) break;
            }
            return;
        }
    } 
    -- tot;
}
void Do() {
    flag = 0;
    int n; cin >> n;
    for(int i = 1; i <= n; ++ i) {
        d[i] = 0;
        G[i].clear();
    }
    for(int i = 1; i <= n; ++ i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        ++ d[u], ++ d[v];
    }
    cir.clear();
    tot = 0;
    for(int i = 1; i <= n; ++ i) {
        vis[i] = 0;
    }
    dfs(1, 0);
    // for(auto i : cir) {
    //     cerr << i << endl;
    // }
    int cnt = 0;
    for(int i = 1; i <= n; ++ i) {
        if(d[i] == 1) ++ cnt;
    }
    int Ans = 0;
    for(int i = 0; i < cir.size(); ++ i) {
        if(d[cir[i]] == 2 && d[cir[(i + 1) % cir.size()]] == 2) {
            Ans = 2;
        } 
        else if(d[cir[i]] == 2) {
            Ans = max(Ans, 1);
        }
    }
    // cerr << "Ans   " << Ans << endl;
    Ans = max(3, Ans + cnt);;
    cout << Ans << "\n";
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    while(T --) {
        Do();
    }
}