G. Remove the Prime
time limit per test
5 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Two players play a game using an array of positive integers. They make alternating moves, the player who cannot make a move loses. In one move you have to choose a prime number $$$p$$$ and a non-empty segment $$$[l;r]$$$ of the array such that all numbers in this segment are divisible by $$$p$$$, and then remove all factors $$$p$$$ from each of them. Removing all factors means that we take a number and divide it by $$$p$$$ while it is divisible.

Determine who wins if both players play optimally.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of array.

The second line contains the array of integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ itself ($$$1 \le a_{i} \le 10^{18}$$$).

Output

Print "First" (without quotes) if first player wins and "Second" (without quotes) otherwise.

Examples
Input
3
2 8 4
Output
First
Input
3
2 12 3
Output
Second