야기엘로니안 대학교(Jagiellonian University)에서는 식물을 매우 사랑한다는 사실은 모두가 알고 있습니다. 우리는 나무, 숲, 심지어 선인장에 관한 수백 개의 문제를 만들었습니다! 안타깝게도 동물에 관한 문제는 그다지 인기가 없습니다. 오늘 우리는 우리가 동물 또한 사랑한다는 것을 증명하고자 합니다.

그래프가 정점의 개수와 간선의 개수가 같은 단순 연결 무향 그래프라면, 이를 해파리(jellyfish)라고 부릅니다. $n$개의 정점을 가진 해파리 $J$가 주어집니다. 임의의 정점 부분집합 $S \subseteq J$에 대하여, 모든 $T \subseteq S$에 대해 $T$의 모든 정점을 포함하고 $S$의 다른 어떤 정점도 포함하지 않는 해파리의 연결 부분 그래프가 존재한다면, $S$를 멋진(awesome) 부분집합이라고 합니다.

해파리 $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