#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int T;
const int NN = 1e5+5;
int N;

bool vis[NN];

int DFS(vector<vector<int>> &EG, int prv, int cur){
    vis[cur] = true;
    for(auto nxt:EG[cur]){
        if(nxt==prv)continue;
        if(vis[nxt]){
            return nxt;
        }
        int ret = DFS(EG, cur, nxt);
        if(ret!=-1)return ret;
    }
    return -1;
}
vector<int> BFS(vector<vector<int>> &EG, int start){
    vector<int> rst;
    queue<pair<int, int>> q;
    vector<int> his(N+1);
    q.push({0, start});
    vis[start] = true;
    his[start] = start;
    while(!q.empty()){
        auto f = q.front();q.pop();
        int prv = f.first, cur = f.second;
        for(auto nxt:EG[cur]){
            if(nxt==prv)continue;
            if(vis[nxt]){
                while(nxt!=start){
                    rst.push_back(nxt);
                    nxt = his[nxt];
                }
                rst.push_back(start);
                reverse(all(rst));
                while(cur!=start){
                    rst.push_back(cur);
                    cur = his[cur];
                }
                return rst;
            }
            vis[nxt] = true;
            his[nxt] = cur;
            q.push({cur, nxt});
        }
    }
}


void sol(){
    vector<vector<int>> EG;
    memset(vis, 0, sizeof(vis));
    cin>>N;
    EG.assign(N+1, vector<int>());
    
    int ans = 0;
    for(int i=0;i<N;i++){
        int u, v;cin>>u>>v;
        EG[u].push_back(v);
        EG[v].push_back(u);
    }
    for(int i=1;i<=N;i++){
        if(EG[i].size()==1)ans++;
    }

    int start = DFS(EG, 0, 1);
    memset(vis, 0, sizeof(vis));
    auto cycle = BFS(EG, start);
    if(cycle.size()==N){
        cout<<3<<'\n';
        return;
    }
    // cout<<start<<'\n';
    // for(auto c:cycle)cout<<c<<' ';cout<<'\n';
    int mx = 0;
    for(int i=0;i<cycle.size();i++){
        if(EG[i].size()==2){
            mx = max(mx, 1);
            if(EG[(i+1)/EG[i].size()].size()==2)mx = max(mx, 2);
        }
    }

    cout<<ans+mx<<'\n';

}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T;
    cin>>T;
    for(int i=0;i<T;i++)sol();
    
    return 0;
}