Treo lại chồi

Cho một cây có gốc gồm $n$ đỉnh, gốc là đỉnh $1$. Với mỗi đỉnh $v$ khác gốc, cha của $v$ là đỉnh liền trước $v$ trên đường đi ngắn nhất từ gốc tới $v$; các đỉnh nhận $v$ làm cha được gọi là con của $v$. Đỉnh không có con được gọi là lá.

Một đỉnh $v$ được gọi là chồi nếu đồng thời thoả mãn ba điều kiện:

• $v$ không phải là gốc,
• $v$ có ít nhất một con,
• mọi con của $v$ đều là lá.

Trong một thao tác, bạn được chọn một chồi $v$ và treo lại nó cùng toàn bộ các con của nó sang một đỉnh khác: xoá cạnh nối $v$ với cha của nó, rồi thêm cạnh nối $v$ với một đỉnh $u$ được chọn tuỳ ý, với điều kiện $u$ không phải là $v$ và cũng không phải con của $v$. Tất cả các con của $v$ vẫn giữ nguyên liên kết với $v$.

Hãy tìm số lá nhỏ nhất mà cây có thể đạt được sau khi thực hiện một số thao tác bất kỳ (có thể là không thao tác nào).

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$: số bộ dữ liệu.
• Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa số nguyên $n$: số đỉnh của cây.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$, cho biết có cạnh nối đỉnh $u$ và đỉnh $v$.

Dữ liệu bảo đảm đồ thị cho trong mỗi bộ dữ liệu là một cây.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số lá nhỏ nhất có thể đạt được.

Ràng buộc

• $1\le t\le {10}^4$
• $2\le n\le 2·{10}^5$
• $1\le u,v\le n$, $u\ne v$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$

Ví dụ