#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> p)
{
    out << "(" << p.first << "," << p.second << ")";
    return out;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> v)
{
    out << "[";
    if (!v.empty())
        cout << v[0];
    for (int i = 1; i < (int)v.size(); i++)
        out << "," << v[i];
    out << "]";
    return out;
}
int solve()
{
    int n;
    cin >> n;
    vector<vector<int>> ve(n + 1);
    vector<int> cnt(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        ve[x].push_back(y);
        ve[y].push_back(x);
        cnt[x]++, cnt[y]++;
    }
    queue<int> qu;
    vector<int> vis(n + 1);
    for (int i = 1; i <= n; i++)
        if (cnt[i] == 1)
        {
            qu.push(i);
        }
    while (!qu.empty())
    {
        int x = qu.front();
        qu.pop();
        vis[x] = 1;
        for (auto it : ve[x])
            if ((--cnt[it] == 1) && vis[it] == 0)
                qu.push(it);
    }
    int ans = 3;
    vector<int> circle;
    vector<int> in_circle(n + 1);
    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            function<void(int)> dfs = [&](int x)
            {
                if (vis[x])
                    return;
                in_circle[x] = 1;
                circle.push_back(x);
                vis[x] = 1;
                for (auto it : ve[x])
                    if (!vis[it])
                        dfs(it);
            };
            dfs(i);
        }
    int single = 0, sum = 0;
    for (auto it : circle)
    {
        if ((int)ve[it].size() == 2)
        {
            single++;
        }
        else
        {

            for (auto t : ve[it])
                if (!in_circle[t])
                {
                    function<void(int, int)> dfs = [&](int x, int h)
                    {
                        if ((int)ve[x].size() == 1 && ve[x].front() == h)
                        {
                            sum++;
                        }
                        for (auto it : ve[x])
                            if (it != h)
                            {
                                dfs(it, x);
                            }
                    };
                    dfs(t, it);
                }
        }
    }
    // cout << "circle=" << circle << endl;
    // cout << single << " " << sum << endl;
    return max(ans, min(single, 2) + sum);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        cout << solve() << "\n";
}