B. ICFC World Finals
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The annual International Collegiate Foosball Contest World Finals are just around the corner, and it just so happens that you're in charge of marketing. Among other things, your job is to design a banner promoting the event. To avoid unnecessary details, you have decided that the banner will only contain the competition ladder, and nothing else.

This year's ladder is a full binary tree consisting of $$$n$$$ nodes. Each internal node has exactly two children. Each node corresponds to a match between two players; the winner of which advances to the match represented by the node's parent. The only exception is the root, representing the grand final, from which no player advances.

The banner should be rectangular, with integer side lengths. The ladder should be drawn on the banner adhering to the following rules:

  • Nodes in the ladder are points on the banner with integer coordinates (relative to the banner's top left corner) and can be drawn on the banner's edges.

  • Edges in the ladder are straight line segments parallel to the sides of the banner connecting nodes on the banner and cannot intersect one another.
  • For each internal node, one of it's children must be drawn to the right of it, and one below it (not necessarily directly)$$$^{\text{∗}}$$$.
  • The bounding boxes of disjoint subtrees must be disjoint $$$^{\text{†}}$$$.

$$$^{\text{∗}}$$$One of the children must have a greater $$$x$$$ coordinate than the parent and the other a smaller $$$y$$$ coordinate.

$$$^{\text{†}}$$$Let $$$Box(T)$$$ be the minimal rectangle with sides parallel to sides of the banner that contains nodes in the subtree $$$T$$$. If two subtrees $$$A$$$ and $$$B$$$ are disjoint, $$$Box(A)$$$ and $$$Box(B)$$$ must also be disjoint (including their perimeter).

Input

The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 200\,000$$$). The descriptions of the test cases follow.

Each test case is given in two lines, the first of which contains the number of nodes in the ladder $$$n$$$ ($$$3 \leq n \leq 200\,000$$$). The next line contains $$$n - 1$$$ integers, the $$$i$$$-th of which denotes the parent of the $$$(i + 1)$$$-th node in the ladder. The root of the ladder is the node $$$1$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.

Output

For every test case, print a single line containing the area of the smallest required banner.

Example
Input
2
5
1 1 3 3
9
1 1 2 2 3 3 6 6
Output
2
6
Note

An optimal placement of nodes in the first sample.

An optimal placement of nodes in the second sample.

An illegal placement of nodes in the second sample. Produces the optimal area; however, the bounding boxes of subtrees rooted at nodes $$$3$$$ and $$$2$$$ intersect.