Ai cũng biết rằng tại Đại học Jagiellonian, chúng tôi rất yêu cây cối. Chúng tôi đã tạo ra hàng trăm bài toán về cây, rừng và thậm chí là xương rồng! Thật không may, các bài toán về động vật lại không phổ biến như vậy. Hôm nay, chúng tôi muốn chứng minh rằng chúng tôi cũng yêu cả động vật nữa.

Chúng tôi gọi một đồ thị là một con sứa (jellyfish) nếu nó là một đồ thị vô hướng đơn, liên thông và có số đỉnh bằng số cạnh. Bạn được cho một con sứa $J$ với $n$ đỉnh. Với một tập hợp con các đỉnh bất kỳ $S \subseteq J$, chúng tôi gọi $S$ là một tập hợp tuyệt vời (awesome subset) nếu với mọi $T \subseteq S$, tồn tại một đồ thị con liên thông của con sứa chứa mọi đỉnh từ $T$ và không chứa bất kỳ đỉnh nào khác từ $S$.

Hãy tìm kích thước lớn nhất có thể của một tập hợp tuyệt vời của $J$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test $z$. Các mô tả của các bộ test sẽ theo sau.

Dòng đầu tiên của mỗi bộ test chứa một số nguyên $n$ ($3 \le n \le 100\,000$) – số lượng đỉnh của con sứa.

$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i$ ($1 \le u_i \neq v_i \le n$), tương ứng với các cạnh của con sứa. Đảm bảo rằng đồ thị đã cho là một con sứa và mỗi cặp hai đỉnh được nối với nhau bởi tối đa một cạnh.

Tổng số lượng đỉnh trong tất cả các bộ test không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng duy nhất chứa một số nguyên – kích thước lớn nhất có thể của một tập hợp tuyệt vời của con sứa.

Ví dụ

Dữ liệu vào 1

2
6
1 2
2 3
3 4
4 1
2 5
2 6
4
1 2
2 3
3 4
4 1

Dữ liệu ra 1

4
3