题目描述

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

• 若为Euclid操作，如果n<p，则他只能新放入p颗石子，否则他可以拿走p的倍数颗石子。
• 若为Pythagoras操作，如果n<q，则他只能新放入q颗石子，否则他可以拿走q的倍数颗石子。 拿光所有石子者胜利。假设他们都以最优策略操作，那么获胜者是谁？

输入格式

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

输出格式

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

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

P
E
R

提示

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

题目来源

鸣谢Claris上传