Giáo sư Pang và Giáo sư Shou thích chơi trò chơi đuổi bắt.

Bản đồ trò chơi bao gồm $n$ phòng và $n - 1$ kênh kết nối hai chiều. Bản đồ trò chơi có tính liên thông, nghĩa là bản đồ tạo thành một cây.

Ban đầu, Giáo sư Pang ở phòng $u$, trong khi Giáo sư Shou ở phòng $v$ ($u \neq v$). Giáo sư Pang và Giáo sư Shou thay phiên nhau chơi, và Giáo sư Shou đi trước. Trong lượt của mình, người chơi biết vị trí của mình và vị trí của người kia, và có thể quyết định ở lại phòng hiện tại hoặc di chuyển đến một phòng khác được kết nối trực tiếp với phòng hiện tại bằng một kênh. Khi Giáo sư Pang và Giáo sư Shou ở cùng một phòng, Giáo sư Shou bị Giáo sư Pang bắt.

Giáo sư Pang và Giáo sư Shou đều rất thông minh. Giáo sư Pang muốn bắt Giáo sư Shou trong một số lượt hữu hạn. Giáo sư Shou không muốn bị Giáo sư Pang bắt trong bất kỳ số lượt hữu hạn nào.

Giáo sư Shou cảm thấy mệt mỏi vì lần nào cũng bị bắt nên đã tìm đến Giáo sư Fei để nhờ giúp đỡ. Giáo sư Shou nhờ Giáo sư Fei thêm một số kênh để Giáo sư Pang không thể bắt được anh ta trong số lượt hữu hạn với bất kỳ cặp phòng ban đầu $(u, v)$ nào. Giáo sư Fei lười biếng, vì vậy ông hy vọng sẽ thêm càng ít kênh càng tốt. Nếu cho dù có thêm kênh như thế nào đi nữa thì vẫn luôn tồn tại một cặp phòng $(u, v)$ sao cho Giáo sư Pang có thể bắt được Giáo sư Shou, hãy in ra $-1$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^4$) biểu thị số lượng bộ dữ liệu kiểm tra.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($2 \le n \le 10^5$) biểu thị số lượng phòng.

Trong $n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n$) biểu thị một kênh kết nối phòng $u$ và phòng $v$.

Đảm bảo rằng tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$, và các phòng cùng các kênh luôn tạo thành một cây.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một số biểu thị số lượng kênh tối thiểu cần thêm vào, hoặc in ra $-1$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

-1
1
-1
2