Alice and Bob went on an adventure, where they found a mysterious array $$$A$$$ consisting of $$$N$$$ positive integers. The $$$i$$$-th element of the array is called $$$A_i$$$.

Alice and Bob decided to play a game with this array, where each player moves in turn, and whoever can't find a valid move loses. Alice goes first. In simple words, Alice makes her move, then it is Bob's move, then it is Alice's move again, and so on. In every move, the player (whose move it is) does the following things sequentially:

1. Select any prime number $$$p$$$ such that there exists an index $$$i$$$ such that $$$p$$$ divides $$$A_i$$$. If no such prime number is found, the player immediately loses.
2. For each element $$$A_j$$$ from the array, if $$$p$$$ divides $$$A_j$$$, replace $$$A_j$$$ by $$$\dfrac{A_j}{p}$$$, else $$$A_j$$$ is kept unchanged. (Note that this part should be done for every element of the array, not just one).
3. The updated array is passed to the next player.