Avoid Coprime Game

For two non-negative integers $x$ and $y$, let $\gcd(x,y)$ be the greatest common divisor of $x$ and $y$ (for $x=0$, let $\gcd(x,y)=\gcd(y,x)=y$). There are $N$ integers on the blackboard, and the $i$\-th integer is $A_i$. The greatest common divisor of these $N$ integers is $1$. Takahashi and Aoki will play a game against each other. After initializing an integer $G$ to $0$, they will take turns performing the following operation, with Takahashi going first. * Choose a number $a$ on the blackboard such that $\gcd(G,a)\neq 1$, erase it, and replace $G$ with $\gcd(G,a)$. The first player unable to play loses. For each $i\ (1\leq i \leq N)$, determine the winner when Takahashi chooses the $i$\-th integer on the blackboard in his first turn, and then both players play optimally. ## Constraints * $2 \leq N \leq 2 \times 10^5$ * $2 \leq A_i \leq 2 \times 10^5$ * The greatest common divisor of the $N$ integers $A_i \ (1\leq i \leq N)$ is $1$. * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\dots$ $A_N$ [samples]