간선 하나를 가진 트리

Alice와 Bob은 루트가 1번 정점인 트리에서 게임을 한다. 토큰을 루트에 놓고 Alice부터 번갈아 토큰을 움직인다. 한 턴에 플레이어는 토큰이 있는 정점에서 그 정점의 자식 중 하나로 토큰을 옮겨야 한다. 자기 턴에 가능한 이동이 없으면 그 플레이어가 진다.

게임을 시작하기 전에 Alice는 트리에 방향 간선 $(u, v)$를 하나 추가할 수 있다. 게임 중에 토큰이 정점 $u$에 있고 추가 간선이 남아 있으면, 현재 플레이어는 토큰을 정점 $v$로 옮길 수 있다. 이때 추가 간선은 삭제되므로 한 게임에서 최대 한 번만 쓸 수 있다.

가능한 $n^2$개의 쌍 $(u, v)$ 중에서, 두 플레이어가 최적으로 플레이할 때 Alice가 이기게 하는 쌍은 몇 개인가? $u = v$도 허용되며, 트리에 이미 있는 간선과 같은 쌍(어느 방향이든)도 허용된다.

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

각 테스트 케이스의 첫 줄에는 정점의 수 $n$ ($2\leq n\leq 2\cdot 10^5$)이 주어진다.

다음 줄에는 루트를 제외한 각 정점의 부모 $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$)이 $n-1$개의 정수로 주어진다.

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

각 테스트 케이스마다 Alice가 이길 수 있게 하는 쌍 $(u, v)$의 개수를 한 줄에 출력한다.

첫 번째 테스트 케이스에서 Alice에게 승리 전략을 주는 간선은 아래 4개이다.