Roy&October之取石子
题目背景
Roy 和 October 两人在玩一个取石子的游戏。
题目描述
游戏规则是这样的:共有 $n$ 个石子,两人每次都只能取 $p^k$ 个( $p$ 为质数,$k$ 为自然数,且 $p^k$ 小于等于当前剩余石子数),谁取走最后一个石子,谁就赢了。
现在 October 先取,问她有没有必胜策略。
若她有必胜策略,输出一行 `October wins!`;否则输出一行 `Roy wins!`。
输入输出格式
输入格式
第一行一个正整数 $T$,表示测试点组数。
第 $2$ 行$\sim$ 第 $T+1$ 行,一行一个正整数 $n$,表示石子个数。
输出格式
$T$ 行,每行分别为 `October wins!` 或 `Roy wins!`。
输入输出样例
输入样例 #1
3
4
9
14
输出样例 #1
October wins!
October wins!
October wins!
说明
对于 $30\%$ 的数据,$1\leq n\leq 30$;
对于 $60\%$ 的数据,$1\leq n\leq 10^6$;
对于 $100\%$ 的数据,$1\leq n\leq 5\times 10^7$, $1\leq T\leq 10^5$。
(改编题)