PO23S1

Uma árvore é um grafo conexo sem ciclos. Uma árvore enraizada tem um vértice especial chamado raiz. O pai de um vértice v (diferente de raiz) é o vértice anterior a v no caminho mais curto da raiz ao vértice v. filhos do vértice v são todos os vértices para os quais v é o pai.

Você recebe uma árvore enraizada com n vértices. O vértice 1 é a raiz. Inicialmente, todos os vértices são saudáveis.

A cada segundo você faz duas operações, a operação de espalhamento e, depois disso, a operação de injeção:

1. Espalhamento: para cada vértice v, se pelo menos um filho de v está infectado, você pode espalhar a doença infectando no máximo um outro filho de v da sua escolha.
2. Injeção: você pode escolher qualquer vértice saudável e infectá-lo.

Esse processo se repete a cada segundo até que toda a árvore esteja infectada. Você precisa encontrar o número mínimo de segundos necessários para infectar toda a árvore.

Entrada

A entrada consiste em vários casos de teste. 

A primeira linha contém um único inteiro t (1 ≤ t ≤ 10⁴) — o número de casos de teste. Segue a descrição dos casos de teste.

A primeira linha de cada caso de teste contém um único inteiro n (2 ≤ n ≤ 2*10⁵) — o número de vértices na árvore fornecida.

A segunda linha de cada caso de teste contém n – 1 inteiros p₂, p₃, …, p_n (1 ≤ p_i ≤n), onde p_i é o ancestral do i-ésimo vértice na árvore.

É garantido que o grafo dado é uma árvore.

É garantido que a soma de n em todos os casos de teste não exceda 2*10⁵.

Saída

Para cada caso de teste, você deve gerar um único inteiro — o número mínimo de segundos necessários para infectar toda a árvore.

Exemplo

entrada

5

7

1 1 1 2 2 4

5

5 5 1 4

2

1

3

3 1

6

1 1 1 1 1

saída

4

4

2

3

4

Observação

A imagem representa a árvore do primeiro caso de teste durante cada segundo.

Um vértice é preto se não estiver infectado. Um vértice é azul se for infectado por injeção durante o segundo anterior. Um vértice é verde se for infectado por propagação durante o segundo anterior. Um vértice é vermelho se for infectado antes do segundo anterior.

Observe que você pode escolher quais vértices são infectados por espalhamento e por injeções.