Prof. Pang과 Prof. Shou는 추격 게임을 즐깁니다.

게임 맵은 $n$개의 방과 $n - 1$개의 양방향 통로로 구성되어 있습니다. 게임 맵은 연결되어 있으며, 이는 맵이 트리 형태임을 의미합니다.

처음에 Prof. Pang은 방 $u$에 있고, Prof. Shou는 방 $v$ ($u \neq v$)에 있습니다. Prof. Pang과 Prof. Shou는 번갈아 가며 행동하며, Prof. Shou가 먼저 시작합니다. 자신의 차례가 되면, 플레이어는 자신의 위치와 상대방의 위치를 알고 있으며, 현재 방에 머무르거나 현재 방과 통로로 직접 연결된 다른 방으로 이동할 수 있습니다. Prof. Pang과 Prof. Shou가 같은 방에 있게 되면, Prof. Shou는 Prof. Pang에게 잡힙니다.

Prof. Pang과 Prof. Shou는 매우 똑똑합니다. Prof. Pang은 유한한 턴 안에 Prof. Shou를 잡으려 하고, Prof. Shou는 유한한 턴 안에 Prof. Pang에게 잡히지 않으려 합니다.

매번 잡히는 것에 지친 Prof. Shou는 Prof. Fei에게 도움을 요청합니다. Prof. Shou는 Prof. Fei에게 어떤 초기 방 쌍 $(u, v)$에 대해서도 Prof. Pang이 유한한 턴 안에 자신을 잡을 수 없도록 통로를 추가해 달라고 부탁합니다. Prof. Fei는 게으르기 때문에 가능한 한 적은 수의 통로를 추가하고 싶어 합니다. 통로를 어떻게 추가하더라도 Prof. Pang이 Prof. Shou를 잡을 수 있는 방 쌍 $(u, v)$가 항상 존재한다면, $-1$을 출력하십시오.

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 방의 수를 나타내는 정수 $n$ ($2 \le n \le 10^5$)이 주어집니다.

다음 $n - 1$개의 줄에는 방 $u$와 방 $v$를 연결하는 통로를 나타내는 두 정수 $u$와 $v$ ($1 \le u, v \le n$)가 주어집니다.

모든 테스트 케이스에 대한 $n$의 합은 $2 \times 10^5$를 넘지 않으며, 방과 통로는 항상 트리를 형성함이 보장됩니다.

출력

각 테스트 케이스마다 추가해야 할 최소 통로의 수를 출력하십시오. 만약 불가능하다면 $-1$을 출력하십시오.

예제

입력 1

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

출력 1

-1
1
-1
2