Alice와 Bob이 $n$개의 정점을 가진 트리 $T$에서 게임을 합니다. Alice는 비밀 정점 $x$를 식별하려고 합니다. 그러나 Bob은 적대적이며 $x$를 미리 선택할 필요가 없습니다.

처음에는 $T$의 모든 정점이 $x$의 "가능한" 후보로 간주됩니다. 각 턴에서 Alice는 정점 $v$를 선택하고 $v$에서 $x$까지의 거리를 질문합니다. Bob은 음이 아닌 정수 $d$로 응답합니다. 그런 다음 Alice는 $\operatorname{dist}(u, v) \neq d$인 모든 후보 정점 $u$를 제거합니다.

Bob의 답변은 적어도 하나의 남은 후보와 일관성이 있어야 합니다. 즉, Alice가 $\operatorname{dist}(u, v) \neq d$인 모든 정점 $u$를 제거한 후에도 후보 집합은 비어 있지 않아야 합니다. 이 규칙을 따르면서 Bob은 Alice가 가능한 한 많은 질문을 사용하도록 강제하기 위해 자신의 답변을 선택합니다.

정확히 하나의 후보 정점이 남으면 Alice가 승리합니다. Alice는 질문 횟수를 최소화하기 위해 최적으로 질문을 선택합니다.

트리의 구조가 주어졌을 때, Alice가 Bob의 전략에 관계없이 승리를 보장하기 위해 필요한 최소 질문 횟수를 구하세요.

예를 들어 Alice가 정점 $v$를 질문하고 Bob이 $d=2$로 답하면, $v$로부터 거리가 정확히 $2$인 모든 정점이 가능한 상태로 남고 나머지 모든 정점은 제거됩니다.

$v$를 질문하고 답 2를 받은 경우: 빗금친 정점이 질문된 정점이고, 점선 정점이 가능한 상태로 남으며, 일반 정점은 제거된다.

입력

첫 번째 줄에는 하나의 정수 $t$ ($1 \le t \le 10^5$)가 주어지며, 이는 테스트 케이스의 수입니다.

각 테스트 케이스는 하나의 정수 $n$ ($2 \le n \le 2000$)으로 시작하며, 이는 정점의 수입니다.

다음 $n-1$개의 줄 각각에는 두 개의 정수 $a_i$와 $b_i$ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$)가 주어지며, 이는 트리의 간선을 나타냅니다.

각 테스트 케이스의 간선들이 트리를 형성하며, 모든 테스트 케이스에 대해 $\sum n^2 \le 2000^2$임이 보장됩니다.

출력

각 테스트 케이스에 대해 하나의 정수를 출력합니다: 최악의 경우 Alice가 필요한 최소 질문 횟수.

예제

입력 1

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

출력 1

1
3

참고 1

• 첫 번째 테스트 케이스에서 트리는 네 개의 정점으로 이루어진 경로입니다. 정점 1을 질문하면 가능한 거리 0, 1, 2, 3이 모두 서로 다르므로 한 번의 질문으로 충분합니다.
• 두 번째 테스트 케이스에서 트리는 정점 1을 중심으로 한 별(star)입니다.
• 다음 그림에서 빗금친 정점은 질문된 정점이고, 점선 정점은 Bob의 답변 후에도 가능한 상태로 남으며, 일반 정점은 제거되었습니다.

질문 2, 답 2: 정점 3, 4, 5가 가능한 상태로 남는다.

질문 3, 답 2: 정점 4, 5가 가능한 상태로 남는다.

질문 4, 답 2: 정점 5만 남는다.

• 이는 세 번의 질문으로 충분함을 보여줍니다. Alice는 먼저 리프 2를 질문합니다. Bob이 0 또는 1로 답하면 비밀 정점이 즉시 결정됩니다. 최악의 답은 2이며, 리프 3, 4, 5가 남습니다. 그런 다음 Alice는 리프 3을 질문하고, 최악의 경우 리프 4, 5가 남습니다. 마지막 한 번의 질문으로 이들을 구별합니다.
• 두 번의 질문으로는 부족합니다. 첫 번째 질문 후에 Bob은 적어도 세 개의 리프를 가능한 상태로 유지할 수 있습니다. 별의 세 리프 중에서 한 번의 추가 거리 질문으로 모두를 구별할 수는 없습니다. 질문한 정점까지의 거리가 적어도 두 리프에서 같기 때문입니다.