The Bytelandian Union

All submissions for this problem are available.

Byteland is a strange country, with many cities, but with a poorly developed road network (in fact, there is exactly one route from each city to any other city, possibly leading through other cities). Until recently, the cities of Byteland were independently governed by proud Mayors, who chose not to integrate too tightly with their neighbours. However, recent opinion polls among Bytelandian computer programmers have shown a number of disturbing trends, including a sudden drop in pizza consumption. Since this had never before happened in Byteland and seemed quite inexplicable, the Mayors sought guidance of the High Council of Wise Men of Byteland. After a long period of deliberation, the Council ruled that the situation was very serious indeed: the economy was in for a long-term depression! Moreover, they claimed that tighter integration was the only way for the Bytelandian cities to survive. Whether they like it or not, the Mayors must now find a way to unite their cities as quickly as possible. However, this is not as easy as it sounds, as there are a number of important constraints which need to be fulfilled:

• Initially, each city is an independent State. The process of integration is divided into steps.
• At each step, due to the limited number of diplomatic envoys available, a State can only be involved in a unification process with at most one other state. At each step two States can unite to form a new State, but only if there exists a road directly connecting some two cities of the uniting States.
• The unification process is considered to be complete when all the cities belong to the same, global State.

The Mayors have asked you to arrange a schedule for the diplomatic talks, so that unification can be completed in as few steps as possible. Can you handle this delicate task?^a)

Input

The first line contains t, the number of test cases (less than 1000). The descriptions of t test cases follow.

Each test case contains the description of the cities of Byteland, given in two lines. The first line contains a single integer k, representing the number of cities in Byteland (2 <= k <= 600); we assume that the cities are numbered 0,...,k-1. The second line contains exactly k-1 integers, and the i-th integer having a value of p represents a road connecting cities having numbers i+1 and p in Byteland.

Output

For each test case, output a separate line containing one number, equal to the minimum number of steps required to perform the unification.

Example

Input:
3
4
0 1 2
8
0 1 2 0 0 3 3
9
0 1 1 1 1 0 2 2

Output:
2
4
5

^a) Some conspiracy theorists claim that this task has in fact nothing to do with unification, and that it was proposed by pizza parlour lobbyists simply to boost their direct revenue at your expense. But don't worry, in any case, you are helping Byteland out of depression!

---

Date:	2008-12-01
Time limit:	40s
Source limit:	50000B
Languages:	All except: PERL6