P4860 Roy & October’s Stone Taking II

Roy and October are playing another stone-taking game. (For Season 1, see P4018.)

The rules are as follows: there are $n$ stones in total. Each turn, a player can only take $p^k$ stones, where $p$ is a prime number, $k = 0$ or $1$, and $p^k$ is less than or equal to the number of stones currently remaining. Whoever takes the last stone wins. Now October moves first. Determine whether she has a winning strategy. If she has a winning strategy, output one line `October wins!`; otherwise output one line `Roy wins!`.

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

Output $T$ lines. Each line should be `October wins!` or `Roy wins!`.

For $30\%$ of the testdata, $1 \le n \le 30$. For $60\%$ of the testdata, $1 \le n \le 10^6$. For $100\%$ of the testdata, $1 \le n \le 5 \times 10^7$, $1 \le T \le 10^5$. Extra: Since the problem setter was too lazy to generate testdata, they directly reused the input from P4018, ovo. Translated by ChatGPT 5