Problem G: Salome Loves Coco [Bonus]

Problem G: Salome Loves Coco [Bonus]

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 77  Solved: 24
[Submit][Status][Web Board]

Description

Salome is a lovely girl, and she is a extreme fan of milk tea. She is a super VIP of Coco, and now she wants to reach all the Coco shops in the world. All the Coco shops are connected as a tree, and the root is the head office. If there is a road between two Coco shops, Salome can go from one to another cost 1. Salome can also go back to head office immediately from any shop cost 0. Initially, Salome go from the head office(node 1), but Salome is short with algorithms. She wants to know the minimum cost if she want to reach all the shops, please tell her the minimum cost.

Input

The first line of the input gives the number of test cases, \(T (1\leq T\leq 10)\). T test cases follow.

For each test case, the first line contains an integer \(n (1\leq n\leq 10^5)\), where n is the number of Coco shops in the world.

The next line contains n-1 integers \(f_2, f_3, · · · , f_n (1\leq f_i < i)\), representing there is a road between \(f_i\) and i.

Output

For each test case, print the minimum cost in one line.

Sample Input

2
3 
1 1 
6 
1 2 3 4 4 

Sample Output

2
6 

HINT

[Submit][Status]