Description

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$)  — the number of vertices in the tree.

Each of the next $n-1$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$), meaning there is an edges between vertices $x$ and $y$ in the tree.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

Output

For each test case print a single nonnegative integer, the minimum number of queries you need, on its own line.

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

0
1
2

Note

In the first test case, there is only one vertex, so you don't need any queries.

In the second test case, you can ask a single query about the node $1$. Then, if $x = 1$, you will get $0$, otherwise you will get $1$.