Thành vẽ một cây (đồ thị vô hướng liên thông không có chu trình) với \(N\) nút được đánh số từ 1 đến \(N\) và muốn tô màu các nút của cây bằng màu đen hoặc trắng. Trên cây, hai nút có thể ghép đôi với nhau khi và chỉ khi chúng thỏa mãn các điều kiện sau:

• cả hai cùng được tô bởi màu trắng, và
• hoặc là có cạnh nối trực tiếp giữa chúng hoặc là có thể nối chúng bởi một đường đi đơn chỉ gồm toàn nút màu đen ngoại trừ hai nút đầu mút là màu trắng.

Yêu cầu: hãy giúp Thành tô màu các nút của cây bằng màu đen hoặc trắng sao cho số lượng cặp nút có thể ghép đôi với nhau là lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên dương \(T\) (\(T\leq 10\)) là số lượng bộ test, mỗi bộ test chứa thông tin về một cây cần tô màu có cấu trúc như sau:

• Dòng thứ nhất chứa một số nguyên dương \(N\) (\(N \leq 5000\)) là số lượng nút của cây;
• Mỗi dòng trong số \(N-1\) dòng tiếp theo chứa hai số nguyên \(x\) \(y\) cách nhau bởi dấu cách cho biết có cạnh nối trực tiếp giữa hai nút \(x\) và \(y\).

Output

• Ghi ra \(T\) dòng, mỗi dòng một số nguyên là kết quả tìm được tương ứng với các bộ test trong dữ liệu vào.

Scoring

• Subtask \(1\): \(T=1\) và \(N\leq 15\)
• Subtask \(2\): \(T=1\) và \(N\leq 20\)
• Subtask \(3\): \(N\leq 500\) và mỗi cây trong dữ liệu vào có đúng 2 lá
• Subtask \(4\): \(N\leq 500\)
• Subtask \(5\): Không có ràng buộc gì thêm

Example

2
8
1 2
2 3
2 4
4 5
5 6
6 7
6 8
2
1 2

7
1