A2491. Roy&October之取石子
编程题
普及/提高-
知识点
题目描述
Roy 和 October 两人在玩一个取石子的游戏。
游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取 $p^k$ 个（ $p$ 为质数，$k$ 为自然数，且 $p^k$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。
现在 October 先取，问她有没有必胜策略。
若她有必胜策略，输出一行
游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取 $p^k$ 个（ $p$ 为质数，$k$ 为自然数，且 $p^k$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。
现在 October 先取，问她有没有必胜策略。
若她有必胜策略，输出一行
October wins!；否则输出一行 Roy wins!。输入格式
第一行一个正整数 $T$，表示测试点组数。
第 $2$ 行$\sim$ 第 $T+1$ 行，一行一个正整数 $n$，表示石子个数。
第 $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$。
对于 $60\%$ 的数据，$1\leq n\leq 10^6$；
对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^7$, $1\leq T\leq 10^5$。