P4018 Roy & October: Taking Stones

Roy and October are playing a stone-taking game.

The rules are as follows: There are $n$ stones in total. On each turn, a player may take exactly $p^k$ stones ($p$ is a prime, $k$ is a natural number, and $p^k$ is less than or equal to the current remaining number of stones). Whoever takes the last stone wins. October moves first. Determine whether she has a winning strategy. If she has a winning strategy, output a line `October wins!`; otherwise, output a line `Roy wins!`.

The first line contains a positive integer $T$, the number of test cases. From line $2$ to line $T+1$, each line contains a positive integer $n$, the number of stones.

$T$ lines, each being either `October wins!` or `Roy wins!`.

For $30\%$ of the testdata, $1 \leq n \leq 30$. For $60\%$ of the testdata, $1 \leq n \leq 10^6$. For $100\%$ of the testdata, $1 \leq n \leq 5\times 10^7$, $1 \leq T \leq 10^5$. (Adapted problem). Translated by ChatGPT 5