Euclidean Nim

Euclid and Pythagoras are the pseudonyms of two Byteotians who love mathematical puzzles. Lately they spend their evenings playing the following game. There is a stack of $n$ stones on the table, and the two friends move alternately. On his move, Euclid either takes any positive multiple of $p$ stones from the stack (allowed only when the stack holds at least $p$ stones) or adds exactly $p$ stones to the stack (allowed only when the stack holds fewer than $p$ stones). Pythagoras moves by the same rule with $q$ in place of $p$: he either takes a multiple of $q$ stones or adds exactly $q$ stones. The player who empties the stack wins. Euclid moves first.

The friends wonder whether they have worked out this game completely. Help them: write a program that determines the result of the game when both players play optimally.

The first line contains one integer $t$ ($1 \le t \le 1000$), the number of test cases. Each of the next $t$ lines describes one test case with three integers $p$, $q$, $n$ ($1 \le p, q, n \le 10^9$).

Print exactly $t$ lines, the answers to the test cases in input order. The answer is the single letter E if Euclid can force a win no matter how Pythagoras plays, P if Pythagoras can force a win no matter how Euclid plays, or R (for remis, the Polish word for a draw) if the game goes on forever.

In the first test case of the sample ($p = 3$, $q = 2$, $n = 1$) Euclid has to add three stones to the stack on his first move. Pythagoras then takes all 4 stones and wins.