Euclid 和 Pythagoras 是两位 Byteotian 人，他们因热爱数学谜题而得名。最近，他们经常在晚上玩以下游戏：桌上有一堆 $n$ 个石子。两人轮流进行操作。Euclid 的操作是：从堆中取走任意 $p$ 的正整数倍个石子（前提是堆中至少有 $p$ 个石子），或者向堆中添加恰好 $p$ 个石子（仅当堆中石子数少于 $p$ 时才能添加）。Pythagoras 的操作类似，但他取走的是 $q$ 的倍数，或者添加恰好 $q$ 个石子。清空石子堆的玩家获胜。Euclid 先手。

朋友们想知道他们是否已经完美掌握了这个游戏。请帮助他们编写一个程序，在双方都采取最优策略的情况下，判断游戏的结果。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。每个测试用例由一行组成，包含三个整数 $p, q$ 和 $n$ ($1 \le p, q, n \le 10^9$)。

输出格式

输出应包含恰好 $t$ 行，对应输入中每个测试用例的结果。答案应为一个字母：‘E’（如果 Euclid 无论 Pythagoras 如何移动都能获胜）、‘P’（如果 Pythagoras 无论 Euclid 如何移动都能获胜）或 ‘R’（表示 remis，即波兰语中的平局，如果游戏会无限进行下去）。

样例

输入 1

4
3 2 1
2 3 1
3 4 5
2 4 3

输出 1

P
P
E
R

说明

在第一个测试用例的游戏中，Euclid 在他的回合必须向堆中添加 3 个石子。多亏了这一点，Pythagoras 可以在他的回合取走全部 4 个石子从而获胜。