## TRIBT - Triangle in Binary Tree

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 isoscele 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^{5})

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.

Added by: | him0727 |

Date: | 2018-04-13 |

Time limit: | 0.5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Own problem |