#4147. [AMPPZ2014]Euclidean Nim

内存限制:256 MiB 时间限制:1 Sec

题目描述

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。

样例

样例输入


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

样例输出


			
P
P
E
R

数据范围与提示

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