题目描述

Euclid和Pythagoras在玩取石子游戏，一开始有$n$颗石子。Euclid为先手，他们按如下规则轮流操作：

• 若为Euclid操作，如果$n<p$，则他只能新放入$p$颗石子，否则他可以拿走$p$的倍数颗石子。
• 若为Pythagoras操作，如果$n<q$，则他只能新放入$q$颗石子，否则他可以拿走$q$的倍数颗石子。

拿光所有石子者胜利。假设他们都以最优策略操作，那么获胜者是谁？

输入格式

第一行包含一个正整数$t$ ($1 \leq t \leq 1000$)，表示数据组数。接下来$t$行，每行三个正整数$p,q,n$ ($1 \leq p, q, n \leq 10^9$)，表示一组数据。

输出格式

输出$t$行。第$i$行输出第$i$组数据的答案，如果Euclid必胜，输出E，如果Pythagoras必胜，输出P，如果游戏永远不会停止，输出R。

输入数据示例

3
2 1 1
2 3 1
3 4 5

输出数据示例

P
E
R

提示

在第一组数据中，Euclid必须新放入3颗石子，然后Pythagoras拿走4颗石子并获胜。

题目来源

鸣谢Claris上传