TreeScript

TreeScript는 트리 구조를 관리하기 위해 만들어진 프로그래밍 언어이다. 이 문제에서는 TreeScript에서 뿌리 있는 트리(rooted tree)를 만드는 방법을 배운다.

TreeScript에서 모든 트리 노드는 메모리에 저장된다. 각 노드는 번호와 부모 노드의 주소를 가진다. 둘 다 변경할 수 없으므로 노드를 만들 때 정해져야 한다. 루트 노드의 부모 주소는 비어 있다.

노드에 접근하려고 노드의 주소를 레지스터에 저장할 수 있다. 레지스터가 $m$개 있으면 레지스터는 $r\[0],r\[1],\ldots ,r\[m-1]$로 나타낸다.

노드 생성문은 $r\[i]=\mathrm{create}(r\[j], k);$ 이다. 여기서 $k$는 노드 번호이고, $i$와 $j$는 레지스터의 인덱스이며 $0\le i,j< m$이다. $i=j$인 경우도 가능하다. 이 문장은 번호가 $k$인 노드를 만든다. 새 노드의 부모 주소는 $r\[j]$에 있고, 만들어진 노드의 주소는 $r\[i]$에 저장된다. 노드가 올바르게 만들어지면 그 주소를 더 저장할 필요가 없다. 노드는 미리 정의된 명령을 자동으로 실행한다. 공간 문제 때문에 이에 대해서는 나중에 배운다.

학습을 확인하려면 크기가 $n$인 뿌리 있는 트리를 만들어야 한다. 시스템이 루트 노드를 만들어 $r\[0]$에 저장하므로, 추가로 실행해야 하는 생성문은 $n-1$개이다.

레지스터는 비싸므로 필요한 레지스터 개수의 최솟값 $m$을 구하라.

테스트케이스가 여러 개 주어진다.

첫 줄에 테스트케이스의 수 $T$ ($1\le T\le 10^5$)가 주어진다.

각 테스트케이스는 다음과 같다.

첫 줄에 트리의 크기 $n$ ($2\le n\le 2\cdot 10^5$)이 주어진다.

둘째 줄에 정수 $p\_1,p\_2,\ldots,p\_n$이 주어진다. 노드 $p\_i$는 노드 $i$의 부모 노드이며 $1\le p\_i< i$이다. 특별히 $p\_1=0$이고, 이는 노드 1이 루트임을 뜻한다.

모든 테스트케이스의 $n$의 합은 $2\times 10^5$을 넘지 않는다.

각 테스트케이스마다 답을 한 줄에 출력한다.