Remove the Prime

Time limit6sMemory limit256 MB

Summary

Each move picks a prime p and a contiguous segment whose entries are all divisible by p, then strips every factor p from those entries; the player unable to move loses.

Level: Medium7 of 10
Topics: Game theory, Number theory, Math
Solved: No attempts yet

Problem

Two players play a game using an array of positive integers. They make alternating moves, and 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 the array.

The second line contains the array $a_1, a_2, \ldots, a_n$ itself ( $1 \le a_i \le 10^{18}$ ).

Output

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

Examples2

Example 1
Input
```
3
2 8 4
```
Expected output
```
First
```
Example 2
Input
```
3
2 12 3
```
Expected output
```
Second
```