Artillery

You are given a tree with N vertices. There is a pawn at one of the vertices.

You have K artillery cannons and you can make a sequence of moves with your cannons. Each move consists of a shot of all cannons at the vertices chosen by you. So, at each move you hit K vertices of the tree. Between two moves, the pawn can either go to the adjacent vertex of the current one or stay in place. After each move the tree doesn’t change. You never know where the pawn is.

Write program that finds the minimum value of K with which you can surely hit the pawn.

From the first line of the input, the program reads the number T of the subtests. For each subtest, the value of N is read from a line and each of the following N ⎼ 1 lines contains two integers describing an edge in the tree. Each edge is given by its two vertices. The vertices of the tree are numbered starting from 0.

Your program should output T lines. On each line, the program should output the minimum value of K for the corresponding subtest.

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100 000

In the first subtest, we can guarantee that we will hit the pawn using 3 canons with the following moves:

1st move: we hit 0, 1 and 4

2nd move: we hit 0, 2 and 5

3rd move: we hit 0, 3 and 6

4th move: we hit 0, 3 and 7

At these moves the pawn will always be hit.

With fewer cannons, the pawn can avoid being hit.