You are given a parent array P of length N that represents a binary tree with N nodes, which may be unbalanced, balanced, complete or full. The array indexes are values in tree nodes and the array values represent the parent node of that particular index, a value -1 means that particular index is the root of the tree. This gives both left child and right child or only left child, for a parent, right child cannot exist without left child. You are required to count the total number of potential isosceles triangles in the binary tree. A potential isosceles triangle is the two sides of equal length must be formed by two paths of equal length from a parent or root. Due to the nature of binary tree, not three sides are connected, you can just ignore the remaining unconnected side.

Consider a parent array [1, 5, 5, 2, 2, -1, 3], it constructs a binary tree like: 

There are 4 potential isosceles triangles in total, they are (1, 5, 2), (0, 5, 4), (3, 2, 4) and (3, 2, 5) respectively.

Input

The first line is the number of test cases T. (1 ≤ T ≤ 50)

For each test case, it starts with one integer representing the number of nodes or length of the array N. (1 ≤ N ≤ 10⁵)

The next line has N integers, P_i is the node's parent node (-1 is the root) and i is its value. (-1 ≤ P_i ≤ N - 1)

Output

Print the total number of potential isosceles triangles.

Example

Input:
3
7
1 5 5 2 2 -1 3
20
-1 0 0 1 1 3 5 4 7 4 8 8 9 10 10 9 15 15 16 16
5
3 0 1 -1 2

Output:
4
20
0

Explanation

Let's visualize the sample input:

Case 1 is just the sample mentioned above.

Case 2 has 20 potential isosceles triangels: (1, 0, 2), (3, 1, 4), (5, 1, 9), (6, 1, 15), (7, 4, 9), (8, 4, 15), (10, 4, 17), (12, 9, 15), (10, 8, 11), (16, 15, 17), (13, 10, 14), (18, 16, 19), (4, 1, 0), (1, 4, 7), (4, 9, 12), (7, 8, 11), (9, 15, 16), (8, 10, 14), (15, 16, 19) and (4, 15, 18).

Case 3 has no triangles.