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

Мы говорим, что граф является медузой, если это простой связный неориентированный граф с одинаковым количеством вершин и ребер. Вам дана медуза J с n вершинами. Для произвольного подмножества вершин S ⊆ J мы говорим, что S является удивительным подмножеством, если для каждого T ⊆ S существует связный подграф медуза, содержащий все вершины из T и не содержащий ни одной другой вершины из S.

Чему равен максимально возможный размер удивительного подмножества J?

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

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

Первая строка каждого теста содержит одно целое число n (3 ≤ n ≤ 105) — количество вершин медузы.

Следующие n строк содержат два целых числа ui, vi (1 ≤ ui ≠ vi ≤ n ) - каждый соответствует ребру медузы. Гарантируется, что данный граф является медузой и каждые две вершины соединены не более чем одним ребром.

Общее количество вершин во всех тестах не превышает 106.

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

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