Remove a Proper Divisor

Difficulty: 1800 6000 ms 128 MB

dp games

A single pile of n stones; a move removes a number of stones equal to some proper divisor of the current pile size (a divisor strictly less than n). The player unable to move loses. For each query n, print the winner.

Input: the first line has Q; each of the next Q lines has a pile size n.

Output: one line per query.

Constraints:

• 1 ≤ Q ≤ 10⁴
• 0 ≤ n ≤ 10⁴

Sample Tests

3
1
6
8

SECOND
FIRST
FIRST

Read the Editorial