Home

Problem Statement

There are $N$ integers written on a blackboard. The $i$-th integer is $A_i$, and the greatest common divisor of these integers is $1$.

Takahashi and Aoki will play a game using these integers. In this game, starting from Takahashi the two player alternately perform the following operation:

• Select one integer on the blackboard that is not less than $2$, and subtract $1$ from the integer.
• Then, divide all the integers on the black board by $g$, where $g$ is the greatest common divisor of the integers written on the blackboard.

The player who is left with only $1$s on the blackboard and thus cannot perform the operation, loses the game. Assuming that both players play optimally, determine the winner of the game.

Constraints

• $1 ≦ N ≦ 10^5$
• $1 ≦ A_i ≦ 10^9$
• The greatest common divisor of the integers from $A_1$ through $A_N$ is $1$.

Sample Input 1

3
3 6 7

Sample Output 1

First

Takahashi, the first player, can win as follows:

• Takahashi subtracts $1$ from $7$. Then, the integers become: $(1,2,2)$.
• Aoki subtracts $1$ from $2$. Then, the integers become: $(1,1,2)$.
• Takahashi subtracts $1$ from $2$. Then, the integers become: $(1,1,1)$.

Sample Input 2

4
1 2 4 8

Sample Output 2

First

Sample Input 3

5
7 8 8 8 8

Sample Output 3

Second