Problem Description

One day, Little A and Little B were happily playing a game together.

They found a tree rooted at node $1$. Obviously, as a tree, it has one or more leaf nodes. Little A and Little B play a turn-based game.

On each turn, Little A or Little B may choose any number of leaf nodes and pick (remove) them from the tree (each time they can only pick leaf nodes; the number picked each time is not limited, but they must pick at least one, and they cannot pick more than the number of existing leaf nodes).

Clearly, after picking some leaves, their parent nodes may become new leaf nodes. At this time, these original parent nodes that have become leaf nodes can also be picked.

Now Little A picks first, then Little B, and they alternate. The person who picks (removes) node $1$ wins. We know Little A and Little B will always play optimally. Determine who will win.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, indicating that there are $T$ test cases.

For each test case, the second line contains a positive integer $n$, indicating that the tree has $n$ nodes.

For each test case, the third line contains $n-1$ integers, representing the parent node index for nodes $2$ through $n$.

Output Format

Output $T$ lines, each containing an integer $1$ or $0$.

$1$ means Little A will win, and $0$ means Little B will win.

2
3
1 1
4
1 2 3

1
0

Hint

The testdata is random. With a simple analysis of the properties, it is easy to get partial points, so this problem uses bundled tests.

For $40\%$ of the testdata: $1 \leq n \leq 100$.

For $100\%$ of the testdata: $1 \leq n \leq 10^6$, $1 \leq T \leq 10$.

The time and memory limits of this problem (especially memory) are very generous. There are no tricky constant-factor limits and no nasty pitfalls, so feel free to solve it.

Translated by ChatGPT 5