#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,mod=1e9+7;
int d[N],n,fa[N];
#define pb push_back
vector<int>g[N];
int ans,mm;
void dfs(int x){
    for(int v:g[x]){
        if(!d[v])d[v]=d[x]+1,fa[v]=x,dfs(v);
        else if(d[v]-d[x]>1){
            int h=v;
            while(h!=x)mm|=(g[h].size()==2&&g[fa[h]].size()==2),h=fa[h];
            mm|=(g[x].size()==2&&g[v].size()==2);
        }
    }
}
void sol(){
    scanf("%d",&n);
    ans=mm=0;
    for(int i=1;i<=n;i++)g[i].clear(),d[i]=0;
    for(int i=1,u,v;i<=n;i++){
        scanf("%d%d",&u,&v);
        g[u].pb(v),g[v].pb(u);
    }
    for(int i=1;i<=n;i++)if(g[i].size()==1)ans++;
    dfs(1);mm++;
    if(!ans)mm++;
    printf("%d\n",ans+mm);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}