Все знают, что в Ягеллонском университете мы очень любим растения. Мы создали сотни задач про деревья, леса и даже кактусы! К сожалению, задачи про животных не так популярны. Сегодня мы хотим доказать, что мы любим и животных тоже.

Мы называем граф «медузой» (jellyfish), если это простой связный неориентированный граф, в котором количество вершин равно количеству ребер. Вам дана медуза $J$ с $n$ вершинами. Для произвольного подмножества вершин $S \subseteq J$ мы называем $S$ «потрясающим» (awesome) подмножеством, если для любого $T \subseteq S$ существует связный подграф медузы, который содержит каждую вершину из $T$ и не содержит никаких других вершин из $S$.

Каков максимально возможный размер потрясающего подмножества медузы $J$?

Входные данные

Первая строка входных данных содержит количество тестов $z$. Далее следуют описания тестов.

Первая строка каждого теста содержит одно целое число $n$ ($3 \le n \le 100\,000$) — количество вершин медузы.

Следующие $n$ строк содержат по два целых числа $u_i, v_i$ ($1 \le u_i \neq v_i \le n$), соответствующих ребрам медузы. Гарантируется, что заданный граф является медузой, и любые две вершины соединены не более чем одним ребром.

Суммарное количество вершин во всех тестах не превышает $10^6$.

Выходные данные

Для каждого теста выведите одну строку, содержащую единственное целое число — максимально возможный размер потрясающего подмножества медузы.

Примеры

Входные данные 1

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

Выходные данные 1

4
3