#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define cmx(x,y) x = max(x,y)
#define cmn(x,y) x = min(x,y)
#define ary(k) array<int,k>
typedef pair<int,int> pii;
typedef vector<int> vi;
void solve(){	
	int n; cin >> n;
	vector<vi> adj(n);
	rep(i,0,n){
		int u,v; cin >> u >> v;
		u--; v--;
		adj[u].PB(v); adj[v].PB(u);
	}
	int leaves = 0,circ = 0;
	rep(i,0,n) if(sz(adj[i]) == 1) leaves++;
	vi vis(n),stk,on(n);
	auto dfs = [&](auto& dfs, int u)->void{
		vis[u] = 1; stk.PB(u);
		for(int v : adj[u]){
			if(!vis[v]) dfs(dfs,v);
			else if(vis[v] == 1){
				for(int i = sz(stk)-1; i >= 0; i--){
					on[stk[i]] = 1;
					if(stk[i] == v) break;
				}
			}
		}
		vis[u] = 2; stk.pop_back();
	};
	dfs(dfs,0);
	rep(i,0,n){
		if(on[i] && sz(adj[i]) == 2) circ++;
	}
	cout << max(3ll,leaves+min(2ll,circ)) << "\n";
}
signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	int t; cin >> t; while(t--) solve();
}