github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: A8
category: NA
old_version: true
problem_code: A8
tags:
    - NA
layout: problem
---
###  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

<pre>
<b>Input:</b>
3
4
0 1 2
8
0 1 2 0 0 3 3
9
0 1 1 1 1 0 2 2

<b>Output:</b>
2
4
5
</pre>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!