The Divisor Game

Difficulty: 1200 2000 ms 128 MB

math games

Starting with N, players alternate replacing N with N − d where d is any proper divisor of N (1 ≤ d < N). A player who cannot move (N = 1) loses. Who wins?

Input: one integer N.

Output: FIRST or SECOND.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

2

FIRST

3

SECOND

Read the Editorial