there is a country which contains n cities connected by n - 1 roads(just like a tree). If you place TNT in one city, all the roads connect these city will be destroyed, now i want to destroy all the roads with the least number of TNT, can you help me ?

Input starts with an integer T(T <= 500), denoting the number of test case.
For each test case, first line contains n(1 <= n <= 1000), denoting the number of cities, next n - 1lines following and each line contains two different cities denoting these two cities connect directly. You can assume the input guarantee the relation among cities is a tree.

For each test case, print the least number of TNT that i need to destroy all the n - 1 roads.