p03810 AtCoder Grand Contest 010 - Decrementing
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 1s 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.

Input

The input is given from Standard Input in the following format:


N
A_1 A_2 … A_N


Output

If Takahashi will win, print `First`. If Aoki will win, print `Second`.

Examples

Input

3
3 6 7


Output

First


Input

4
1 2 4 8


Output

First


Input

5
7 8 8 8 8


Output

Second
```python
#d
#the niumbers of evens is important
#the point is, there is no influence to odd/even if you divide them by odd numbers.
#You should do simulation only in the case where there is one odd over 3 and even numbers of even numbers

from fractions import gcd

def count(a):
    odd, even = 0,0
    for x in a:
        if x % 2 == 1: odd = odd + 1
        else: even = even + 1
    return odd,even

def deal(n,a):
    odd,even = count(a)
    if even == 0:
        return False
    if even % 2 == 1:
        return True
    if odd > 1:
        return False
    
    #the case where there is one odd (over 3) and even numbers of even numbers
    #calculate gcd by step by step
    #if you write g = 1, it is a lie.
    if a[0] % 2 == 0:
        g = a[0]
    else:
        g = a[1]
        
    for i in range(0,n):
        if a[i] % 2 == 1:
            if a[i] == 1: 
                return False
            a[i]  -= 1
        g = gcd(a[i], g)
    return not deal(n,list(map(lambda x: x//g,a)))

n = int(input())
a = [int(i) for i in input().split()]
if deal(n,a):
    print('First')
else:
    print('Second')

```