#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct graph{
    int head[N],nxt[N<<1],to[N<<1],cnt;
    graph():cnt(1){}
    void add(int u,int v){
        nxt[++cnt]=head[u];
        to[cnt]=v;
        head[u]=cnt;
    }
}gr;
int n,fa[N];
bool vis[N<<1];
bool tag[N];
vector<int> cir;
bool incir[N];
void dfs(int u){
    tag[u]=true;
    for(int i=gr.head[u];i;i=gr.nxt[i]){
        if(vis[i])continue;
        vis[i]=vis[i^1]=true;
        int v=gr.to[i];
        if(tag[v]){
            int t=u;
            while(t!=v){
                incir[t]=true;
                cir.push_back(t);
                t=fa[t];
            }
            incir[v]=true;
            cir.push_back(v);
            break;
        }else{
            fa[v]=u;
            dfs(v);
        }
    }
}
int sz[N];
int tot;
void dfs_tree(int u,int fa){
    sz[u]=1;
    for(int i=gr.head[u];i;i=gr.nxt[i]){
        int v=gr.to[i];
        if(incir[v])continue;
        if(v==fa)continue;
        dfs_tree(v,u);
        sz[u]+=sz[v];
    }
    if(sz[u]==1)tot++;
}
void clear(){
    for(int i=2;i<=gr.cnt;i++){
        vis[i]=false;
    }
    gr.cnt=1;
    for(int i=1;i<=n;i++){
        gr.head[i]=0;
        incir[i]=false;
        tag[i]=false;
        fa[i]=0;
        sz[i]=0;
    }
    tot=0;
    cir.clear();
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        gr.add(u,v);
        gr.add(v,u);
    }
    dfs(1);
    int ans=0;
    int d=0;
    for(auto x:cir){
        tot=0;
        dfs_tree(x,0);
        if(sz[x]>1){
            ans+=tot;
            d++;
        }
    }
    if(d==0){
        cout<<min(3,(int)cir.size())<<'\n';
    }else if(d==1){
        cout<<ans+min((int)cir.size()-1,2)<<'\n';
    }else{
        int las=-1;
        int mx=0;
        int fir=-1;
        for(int i=0;i<cir.size();i++){
            int x=cir[i];
            if(sz[x]>1){
                mx=max(mx,min(i-las-1,2));
                if(fir==-1){
                    fir=i;
                }
                las=i;
            }
        }
        mx=max(mx,min(2,(int)cir.size()-(las-fir+1)));
        cout<<ans+mx<<'\n';
    }
    clear();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}