G - Divisor Game
Milk
2
s
1024
MB
100
点
問題文
itigo くんと Today くんは Divisor Game というゲームで遊んでいます。
Divisor Game のルールは次のとおりです。
- 開始時には $N$ 個の石がある
- $2$ 人のプレイヤーが itigo くんから順に、交互に次の操作を行う
- 残りの石の個数を $x$ とする。$x$ の正の約数のうち好きな数を選び、その数だけ石を捨てる
- 操作を行った結果、残りの石の個数が $1$ 個以下になったとき、その操作を行ったプレイヤーが負けで、負けでない方が勝ちとなる
互いに最適に行動したとき、先手の itigo くんと後手の Today くんのどちらが勝つか判定してください。
なお、このゲームは必ず有限回の操作で勝敗がつくことが証明できます。
制約
- $2 \leq N \leq 10^{9}$
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられます。
$N$
出力
先手の itigo くんが勝つ場合は First
、後手の Today くんが勝つ場合は Second
と出力してください。
入力例 1
3
出力例 1
First
例えば、ゲームは以下のように進行します。
- 先手の itigo くんが $3$ の約数から $1$ を選択する。石の個数は $2$ となる。
- $2$ の約数は $1$ と $2$ であり、どちらを選択しても石の個数は $1$ 以下となる。したがって後手の Today くんは負けとなり、先手の itigo くんが勝ちとなる。
実際には、このケースでは先手の itigo くんが最適な行動を取れば常に itigo くんが勝者となることを示せます。
したがって、First
と出力してください。
入力例 2
378292877
出力例 2
Second