I. The magic sock
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a fantastic world there exists a special magic sock, and in this world live two mischievous elves, Dobby and Winky, who love creating and playing with magical objects.

Full of creativity, Dobby and Winky work together to bring new magical objects to life. Inspired by their fascination, they create a shimmering bridge of light, connecting each new object to another. This connection can be made with the special magic sock or with any other magical object that is already connected through the existing light bridges to the magic sock. It's like they weave a magic web with their own hands! In this way, they shape their "magic tree", a reflection of their imagination and spirit.

After creating their masterpiece, Dobby and Winky embark on the competitive part of the game. Instead of adding more objects, they take turns removing light bridges. Each turn, a player removes a single light bridge, causing magical objects, and the light bridges connecting them, that are no longer linked to the magic sock to vanish into thin air. Whoever gets to play when only the magic sock is left loses, as they cannot eliminate any bridge.

Dobby and Winky have repeated this game numerous times, creating magical trees and then destroying them, so they have become experts at the game, but are already a little tired of playing. For the next magic trees they had in mind, they want you to tell them whether the first or second player wins, taking into account that both of them play optimally.

Input

The input consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Each test case is made up of two lines.

The first line of each case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the number of objects in the magic tree.

Each object is represented by a number from $$$1$$$ to $$$n$$$, with the magic sock being represented by the number $$$1$$$.

The second line of each case contains $$$n-1$$$ integers $$$o_2, o_3, \dots, o_n$$$ ($$$1 \le o_i \lt i$$$) — the object to which each non-special object in the tree was connected.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print $$$1$$$ if the first player has a winning strategy or $$$2$$$ if the second player has a winning strategy.

Example
Input
4
3
1 2
3
1 1
4
1 1 1
7
1 2 2 1 5 5
Output
1
2
1
2
Note
(a) Magic tree created by Dobby and Winky.

(b) Magic tree after the first player removes the bridge between object 1 and object 2.

The first player has a winning strategy. On his first turn, he deletes the bridge connecting object 2 to object 1. This causes objects 2 and 3, and the bridge connecting them, to disappear (see Fig. 1(b)). On the second player's turn, only object 1 remains, which is not connected to any other object. The second player has no valid moves and loses the game.
(a) Magic tree created by Dobby and Winky.

(b) Magic tree after the first player eliminates the bridge between object 1 and object 2

(c) Magic tree after the second player eliminates the bridge between object 1 and object 3.

Regardless of the first player's initial move, the second player has a winning strategy. If the first player removes the bridge connecting object 2 to object 1, object 2 disappears. On the second player's turn, only objects 1 and 3 connected by a bridge remain (see Fig. 2(b)). The second player can eliminate the only bridge causing object 3 to disappear. Then, when it is the first player's turn again, only object 1 will remain (see Fig. 2 (c)), he will not be able to play and, therefore, will lose the game. With an analogous analysis it can be shown that if the first player eliminates in his first turn the bridge connecting object 3 with 1, in the second turn of the first player there will again only be object 1 and, therefore, also the first player will lose the game in this case.