Facebook Hacker Cup 2015 Round 1

The fine people of Corpro Corp. are a festive bunch. Every holiday season, everybody buys a gift for their manager. A cynic might say that the employees are just trying to bribe their way to a better performance review, but if you asked them yourself, they'd say they just wanted to spread cheer.

The fine people of Corpro Corp. are a frugal bunch. When they buy gifts, they cooperate to collectively buy the least expensive gifts that they can. A cynic might say that the employees are cheap, but if you asked them yourself, they'd say it's the thought that counts.

There are $N$ employees working at Corpro Corp., and each of them has a manager, except for the CEO who has no manager (the CEO also buys a gift every year, but she donates it to charity).
The employees each have a unique employee ID which is an integer from $1$ to $N$. As you might expect, the CEO has the ID $1$.

If there exists a set of two or more employees $\{p_1,\dots ,p_k\}$ such that, for all $i<k$, $p_i$ is the manager of $p_{i+1}$, then we say that $p_1$ is "responsible for" $p_k$.
There are never two employees who are responsible for each other.
That would be a silly hierarchy indeed.

There are $N$ kinds of gifts available for purchase, and the $i^{\text{th}}$ kind of gift costs $i$ dollars. That is, the prices of the different kinds of gifts are $\{\$1,\$2,\$3,\dots ,\$N\}$. There are $N$ copies of each gift available for purchase.

The only thing that stops all employees from purchasing gifts that cost $\$1$ is the awkwardness of buying a gift for their manager that's the same as the one their manager is giving away. No employee would ever do such a thing!

For example, in a company with just 2 employees, at least $\$3$ must be spent in total. If employee #1 (the CEO) buys a $\$1$ gift to donate to charity, then employee #2 cannot buy a $\$1$ gift for employee #1 (their manager), but they can buy a $\$2$ gift instead. Note that it would be equally optimal for the CEO to buy a $\$2$ gift, while receiving a $\$1$ gift from her subordinate.

What's the minimum possible total expenditure across the whole company during the gift exchange?

Input

Input begins with an integer $T$, the number of corporate hierarchies to consider.
Each hierarchy is made up of two lines.
The first line contains the integer $N$.
The second line contains $N$ space-separated integers.
The $i^{\text{th}}$ integer is the employee ID of the manager of employee $i$, with the exception that the first integer is always $0$, denoting that the CEO has no manager.

Output

For the $i^{\text{th}}$ hierarchy, print a line containing Case #i: followed by the smallest amount of money the entire company would need to spend.

Constraints

$1\le T\le 100$
$1\le N\le 200000$

NOTE: The input file is about 10-20MB.

Explanation of Sample

In the first test case, the CEO will spend $\$2$, and the other employees will spend $\$1$.

In the second test case, employees #2 and #3 will spend $\$2$, and the other employees will spend $\$1$.

Sample Input

5
3
0 1 1
8
0 1 1 2 2 3 3 3
5
0 1 2 3 4
9
0 1 2 3 4 5 5 5 5
8
0 1 1 1 1 2 2 2

Sample Output

Case #1: 4
Case #2: 10
Case #3: 7
Case #4: 12
Case #5: 11