#P1905B. Begginer's Zelda

Begginer's Zelda

Description

You are given a tree^{\dagger}. In one zelda-operation you can do follows:

  • Choose two vertices of the tree uu and vv;
  • Compress all the vertices on the path from uu to vv into one vertex. In other words, all the vertices on path from uu to vv will be erased from the tree, a new vertex ww will be created. Then every vertex ss that had an edge to some vertex on the path from uu to vv will have an edge to the vertex ww.
Illustration of a zelda-operation performed for vertices 11 and 55.

Determine the minimum number of zelda-operations required for the tree to have only one vertex.

^{\dagger}A tree is a connected acyclic undirected graph.

Each test consists of multiple test cases. The first line contains a single integer tt (1t1041 \le t \le 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer nn (2n1052 \le n \le 10^5) — the number of vertices.

ii-th of the next n1n − 1 lines contains two integers uiu_i and viv_i (1ui,vin,uivi1 \le u_i, v_i \le n, u_i \ne v_i) — the numbers of vertices connected by the ii-th edge.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.

Input

Each test consists of multiple test cases. The first line contains a single integer tt (1t1041 \le t \le 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer nn (2n1052 \le n \le 10^5) — the number of vertices.

ii-th of the next n1n − 1 lines contains two integers uiu_i and viv_i (1ui,vin,uivi1 \le u_i, v_i \le n, u_i \ne v_i) — the numbers of vertices connected by the ii-th edge.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

Output

For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.

样例输入 1

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

样例输出 1

1
3
2
2

Note

In the first test case, it's enough to perform one zelda-operation for vertices 22 and 44.

In the second test case, we can perform the following zelda-operations:

  1. u=2,v=1u = 2, v = 1. Let the resulting added vertex be labeled as w=10w = 10;
  2. u=4,v=9u = 4, v = 9. Let the resulting added vertex be labeled as w=11w = 11;
  3. u=8,v=10u = 8, v = 10. After this operation, the tree consists of a single vertex.