포병

트리가 주어진다. 트리의 정점 $N$개 중 한 정점에 폰이 놓여 있다.

$K$개의 포병 대포가 있고, 대포로 연속된 이동을 할 수 있다. 각 이동은 선택한 정점들에 모든 대포를 쏘는 것이다. 따라서 매 이동마다 트리의 정점 $K$개를 맞힌다. 두 이동 사이에 폰은 인접한 정점으로 가거나 제자리에 머물 수 있다. 각 이동 후에도 트리는 변하지 않는다. 폰이 어디 있는지는 알 수 없다.

폰을 반드시 맞힐 수 있는 $K$의 최솟값을 구하라.

첫 줄에 부분 테스트의 개수 $T$가 주어진다. 각 부분 테스트마다 한 줄에 $N$이 주어지고, 이어서 $N-1$개의 줄에 트리의 간선을 나타내는 두 정수가 주어진다. 정점은 0부터 번호가 매겨진다.

$T$줄을 출력한다. 각 줄에는 해당 부분 테스트의 $K$ 최솟값을 출력한다.

$1 \le T \le 10$

$1 \le N \le 100\,000$

첫 번째 부분 테스트에서는 대포 3개로 다음 이동을 하면 폰을 반드시 맞힐 수 있다.

1번째 이동: 0, 1, 4를 맞힌다

2번째 이동: 0, 2, 5를 맞힌다

3번째 이동: 0, 3, 6을 맞힌다

4번째 이동: 0, 3, 7을 맞힌다

이 이동에서는 폰이 항상 맞는다. 대포가 더 적으면 폰이 맞지 않게 피할 수 있다.