Cho cây ~n~ đỉnh, mỗi đỉnh được tô một trong ~2~ màu trắng hoặc đen. Một cặp đỉnh ~(u, v)~ có thể ghép đôi với nhau khi và chỉ khi thỏa mãn đồng thời:

• ~u~ và ~v~ được tô màu trắng

• Các đỉnh trên đường đi đơn của từ ~u \rightarrow v~ được tô toàn màu đen (trừ ~u~ và ~v~)

Yêu cầu tô màu đỉnh của cây sao cho tạo được nhiều cặp ~(u, v)~ có thể ghép đôi với nhau nhất.

Input

Dòng đầu tiên chứa một số nguyên dương (~T \leq 10~) là số lượng test.

Ở mỗi test:

• Dòng đầu tiên của test chứa số nguyên dương ~N~ (~N \leq 5000~) là số lượng nút của cây.

• ~N - 1~ dòng tiếp theo chứa hai số nguyên ~u, v~ (~1 \leq u, v \leq n~) là cạnh của cây. Dữ liệu đảm bảo đồ thị sẽ là cây

Output

Ghi ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả tương ứng với bộ test.

Sample Input 1

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

Sample Output 1

5
2

Sample Input 2

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

Sample Output 2

2
6

Notes

Ở ví dụ 1, test đầu tiên, ta tô màu đỉnh ~2~ để có được ~5~ cặp ~(1, 4)~, ~(1, 3)~, ~(3, 4)~, ~(3, 6)~, ~(5, 6)~.

Ở ví dụ 2, test thứ hai, ta cũng tô màu đỉnh ~2~ để có được ~6~ cặp ~(1, 3)~, ~(1, 4)~, ~(1, 5)~, ~(3, 4)~, ~(3, 5)~, ~(4, 5)~.