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:
$$$^{\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).
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$$$.
For every test case, print a single line containing the area of the smallest required banner.
2 5 1 1 3 3 9 1 1 2 2 3 3 6 6
2 6
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.