该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

You are given a tree consisting of n vertices numbered 1 to n rooted at node 1. The parent of the i-th vertices is pi. You can move from a vertex to any of its children. What's more, you can add one directed edge between any two different vertices, and you can move through this edge too. You need to maximize the number of pairs (x,y) such that x can move to y through the edges after adding the edge. Note that x can also move to x.

Input Format

The first line contains one integer T (1≤T≤100000) — the number of test cases.

The first line of each test case contains only one integer n($1≤n≤5×10​^5$​) — the number of vertices in the tree.

The second line of each test case contains n−1 integers p2,p3,…,pn(1≤pi<i)the parent of each non-root node.**

The sum of n over all test cases does not exceed $10​^6$​.

Output Format

Print T integers — for each test case output the maximum number of pairs (x,y) that vertices x can move to y after adding one edge.

2
5
1 1 2 2
6
1 2 3 1 3​

17
26