#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, int>> st;
#define MAX 1010101
vector<int> adj[MAX];
int p[MAX];
int find(int a) {
	if (p[a] == a) return a;
	return p[a] = find(p[a]);
}
bool uni(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	p[a] = b;
	return true;
}
vector<int> path;
bool dfs(int x, int e, int p = 0) {
	path.push_back(x);
	if (x == e) return true;
	for (auto v : adj[x]) if (v != p && dfs(v, e, x)) return true;
	path.pop_back();
	return false;
}
int chk[MAX];
int dp[MAX];
int sz[MAX];
void calc(int x, int p = 0) {
	dp[x] = 0;
	for (auto v : adj[x]) {
		if (~chk[v]) continue;
		if (v == p) continue;
		sz[x] = 1;
		calc(v, x);
		dp[x] += dp[v];
	}
	if (!sz[x]) dp[x] = 1;
}
void solve() {
	int N;
	cin >> N;
	int i, a, b;
	int s, t;
	s = t = 0;
	path.clear();
	for (i = 1; i <= N; i++) p[i] = i, dp[i] = sz[i] = 0, adj[i].clear(), chk[i] = -1;
	for (i = 1; i <= N; i++) {
		cin >> a >> b;
		if (uni(a, b)) {
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		else s = a, t = b;
	}
	assert(s && t);
	dfs(s, t);
	int M = path.size();
	for (i = 0; i < M; i++) chk[path[i]] = i;
	for (auto v : path) calc(v);
	int ans = 3;
	int dpsum = 0;
	int scnt = 0;
	for (auto v : path) {
		if (sz[v]) dpsum += dp[v];
		else scnt++;
	}
	for (i = 0; i < M; i++) {
		int c = path[i];
		int n = path[(i + 1) % M];
		int res = dpsum + 2;
		if (sz[c]) res -= dp[c];
		if (sz[n]) res -= dp[n];
		ans = max(ans, res);
	}
	ans = max(ans, dpsum + (scnt > 0));
	cout << ans << '\n';
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T--) solve();
}