Background

Roy and October are playing a stone-taking game.

Problem Description

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

Input Format

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.

Output Format

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

3
4
9
14

October wins!
October wins!
October wins!

Hint

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