Remove a Perfect Power

Difficulty: 1800 6000 ms 128 MB

dp games

A single pile of n stones; a move removes a perfect power (4, 8, 9, 16, 25, 27, ... — a^b with b ≥ 2) or 1. 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
0
4
9

SECOND
FIRST
FIRST

Read the Editorial