Background

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

Problem Description

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!.

Input Format

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 Format

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

3
5
7
14

October wins!
October wins!
October wins!

Hint

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