Alice và Bob đang chơi một trò chơi trên một cây $T$ có $n$ đỉnh. Alice muốn xác định một đỉnh bí mật $x$. Tuy nhiên, Bob có tính đối kháng và không cần phải chọn $x$ trước.

Ban đầu, mỗi đỉnh của $T$ được coi là một ứng cử viên "khả dĩ" cho $x$. Trong mỗi lượt, Alice chọn một đỉnh $v$ và hỏi khoảng cách từ $v$ đến $x$. Bob trả lời một số nguyên không âm $d$. Alice sau đó loại bỏ mọi ứng cử viên $u$ sao cho $\operatorname{dist}(u, v) \neq d$.

Câu trả lời của Bob phải nhất quán với ít nhất một ứng cử viên còn lại. Nói cách khác, sau khi Alice loại bỏ tất cả các đỉnh $u$ với $\operatorname{dist}(u, v) \neq d$, tập ứng cử viên vẫn phải không rỗng. Tuân theo quy tắc này, Bob chọn câu trả lời của mình để buộc Alice sử dụng càng nhiều truy vấn càng tốt.

Alice thắng ngay khi chỉ còn đúng một ứng cử viên. Alice chọn các truy vấn của mình một cách tối ưu để giảm thiểu số lượng truy vấn.

Cho cấu trúc của cây, hãy tìm số lượng truy vấn tối thiểu mà Alice cần để đảm bảo chiến thắng, bất kể chiến lược của Bob.

Ví dụ, nếu Alice truy vấn một đỉnh $v$ và Bob trả lời $d=2$, thì tất cả các đỉnh ở khoảng cách chính xác $2$ từ $v$ vẫn còn khả dĩ, và tất cả các đỉnh khác bị loại bỏ.

Truy vấn $v$ và nhận được câu trả lời 2: đỉnh được tô sọc là đỉnh được truy vấn, các đỉnh chấm chấm vẫn còn khả dĩ, và các đỉnh trơn đã bị loại bỏ.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^5$), số lượng bộ dữ liệu.

Mỗi bộ dữ liệu bắt đầu với một số nguyên $n$ ($2 \le n \le 2000$), số lượng đỉnh.

Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$), biểu diễn một cạnh của cây.

Dữ liệu đảm bảo rằng các cạnh của mỗi bộ dữ liệu tạo thành một cây và tổng $\sum n^2 \le 2000^2$ trên tất cả các bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên: số lượng truy vấn tối thiểu mà Alice cần trong trường hợp xấu nhất.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
3

Ghi chú 1

• Trong bộ dữ liệu thứ nhất, cây là một đường đi gồm bốn đỉnh. Truy vấn đỉnh 1 cho các khoảng cách khả dĩ 0, 1, 2, 3, tất cả đều phân biệt, do đó một truy vấn là đủ.
• Trong bộ dữ liệu thứ hai, cây là một ngôi sao với tâm là đỉnh 1:
• Trong các hình dưới đây, đỉnh được tô sọc là đỉnh được truy vấn, các đỉnh chấm chấm vẫn còn khả dĩ sau câu trả lời của Bob, và các đỉnh trơn đã bị loại bỏ.

Truy vấn 2, câu trả lời 2: các đỉnh 3, 4, 5 vẫn còn khả dĩ.

Truy vấn 3, câu trả lời 2: các đỉnh 4, 5 vẫn còn khả dĩ.

Truy vấn 4, câu trả lời 2: chỉ còn đỉnh 5.

• Điều này cho thấy ba truy vấn là đủ. Alice trước tiên truy vấn lá 2. Nếu Bob trả lời 0 hoặc 1, bí mật được xác định ngay lập tức; câu trả lời xấu nhất là 2, để lại các lá 3, 4, 5. Sau đó Alice truy vấn lá 3, và trong trường hợp xấu nhất, các lá 4, 5 vẫn còn. Một truy vấn cuối cùng phân biệt chúng.
• Hai truy vấn là không đủ. Sau truy vấn đầu tiên, Bob có thể giữ ít nhất ba lá còn khả dĩ. Trong ba lá của một ngôi sao, một truy vấn khoảng cách nữa không thể phân biệt tất cả chúng, vì ít nhất hai trong số các lá có cùng khoảng cách đến đỉnh được truy vấn.