Zagha and Hiasat are playing a game on a tree with $n$ nodes. At the beginning, both players are assigned a starting node on the tree, the two starting nodes are different, then both players take turns alternately. In each turn, the player chooses an *unassigned* adjacent node and merges it with his current node.
To merge node $a$ with node $b$, we remove the edge $(a, b)$, remove the node $b$, and then any edge $(b, x)$ for any node $x$ becomes $(a, x)$.
Zagha will start first, and the player who can't make a move loses. In how many ways we can choose the starting positions for Zagha and Hiasat such that Zagha is guaranteed to win (if both play optimally)?
The first line of input contains a single integer $T$ ($1 <= T <= 15000$), the number of test cases.
The first line of each test case contains a single integer $n$ ($1 <= n <= 10^6$), the size of the tree.
The second line contains $n -1$ space-separated integers $a_2, a_3,..., a_n$ ($1 <= a_i <= n$), representing that there is an edge between node $i$ and $a_i$.
The sum of $n$ over all test cases doesn't exceed $4 times 10^6$.
For each test case, output a single line with the number of ways to choose the starting positions for Zagha and Hiasat such that Zagha is guaranteed to win.
In the second sample, there are 6 ways to choose the starting positions. Zagha is guaranteed to win in 4 of them.
## Input
The first line of input contains a single integer $T$ ($1 <= T <= 15000$), the number of test cases.The first line of each test case contains a single integer $n$ ($1 <= n <= 10^6$), the size of the tree.The second line contains $n -1$ space-separated integers $a_2, a_3,..., a_n$ ($1 <= a_i <= n$), representing that there is an edge between node $i$ and $a_i$.The sum of $n$ over all test cases doesn't exceed $4 times 10^6$.
## Output
For each test case, output a single line with the number of ways to choose the starting positions for Zagha and Hiasat such that Zagha is guaranteed to win.
[samples]
## Note
In the second sample, there are 6 ways to choose the starting positions. Zagha is guaranteed to win in 4 of them.
**Definitions**
Let $ T = (V, E) $ be a tree with $ n = |V| $ nodes.
Let $ S \subseteq V \times V $ be the set of ordered pairs $ (u, v) $ such that $ u \ne v $, representing possible starting positions for Zagha ($ u $) and Hiasat ($ v $).
**Game Rules**
- Players alternate turns, Zagha moves first.
- On a turn, a player must choose an *unassigned* neighbor of their current node and *merge* it into their node (removing the edge and the merged node, redirecting its other edges).
- A player loses if they cannot make a move.
- All moves are optimal.
**Objective**
Count the number of ordered pairs $ (u, v) \in S $ such that Zagha has a winning strategy under optimal play.
**Constraints**
1. $ 1 \le T \le 15000 $
2. For each test case: $ 1 \le n \le 10^6 $, and the sum of all $ n $ across test cases $ \le 4 \times 10^6 $
3. The tree is given via parent representation: for $ i = 2 $ to $ n $, node $ i $ is connected to node $ a_i $
**Output**
For each test case, output the number of starting position pairs $ (u, v) $ where Zagha wins.