N cities named with numbers 1 ... N are connected with n-1 two-way roads. We say two cities A and B are connected, if and only if there is a road between A and B, or there exists a city C such that there is a road between A and C, and C and B are connected.

       a city is important if and only if other two cities connected by it. Your job is to calculate the number of important cities.

The first line of the input contains an integer T (1<=T<=10) which means the number of test cases. Then T blocks follow, each block starts with a number N (1<=N<=10^5). Followed by N-1 line, each line contains two integer A B (1 <= A, b <= N) which means the road connected A and B.

Each test output one line contains a number about important cities.

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

1
2
3