Hassan and his friend Naya are nerds at math and are always fighting about who is better, as they are in the same class. One day their coach Bassam decided to give them an array $$$A$$$ of size $$$N$$$ and they will play the following game alternately for $$$N-1$$$ rounds.

Naya plays first, at each round a player takes any two elements $$$X$$$, $$$Y$$$ from the array, erases them, then adds $$$\gcd(X,Y)$$$ to the end of $$$A$$$. It can be shown that after $$$N-1$$$ rounds $$$A$$$ will have only one element.

For example, let $$$A=[3,8,5,12,1]$$$, if a player chooses $$$8$$$ and $$$12$$$, then $$$A$$$ becomes $$$[3,5,1,4]$$$.

Naya wins if at the end of the game $$$A=[1]$$$, otherwise Hassan wins. Your task is to find the winner of the game, knowing that both players play optimally.

Here, $$$\gcd(X,Y)$$$ denotes the greatest common divisor for $$$X$$$ and $$$Y$$$, for example $$$\gcd(12,8)=4$$$ and $$$\gcd(15,14)=1$$$.