|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||4||4||4||100.000%|
Euclid and Pythagoras are pseudonyms of two Byteotians for their love of mathematical puzzles. Lately, they spend evenings playing the following game. There is a stack of n stones on the table. Friends perform alternating moves. Euclid's move consists of taking any positive multiple of p stones from the stack (providing the stack contains at least p stones) or adding exactly p stones to the stack-adding the stones is possible, however, only in case the stack contains less than p stones. Pythagoras' move is analogical, except that either he takes a multiple of q stones, or adds exactly q stones. The winner is the player who empties the stack. Euclid begins the game.
Friends wonder whether they have worked out this game perfectly. Help them and write a program that will state what should be the result of the game, providing both players are making optimal moves.
The first line of input contains one integer t (1 ≤ t ≤ 1,000) denoting the number of test cases described in the following part of the input. Description of one test case consists of one line containing three integers p, q and n (1 ≤ p, q, n ≤ 109).
Output should include exactly t lines containing answers to the subsequent test cases from input. The answer should be one letter
E (if Euclid could bring about his victory, regardless of the Pythagoras' movements),
P (if Pythagoras could bring about his victory, regardless of Euclid's moves) or
R (for remis, i.e. draw in Polish, if the game will be played infinitely).
4 3 2 1 2 3 1 3 4 5 2 4 3
P P E R
In the game from the first test case Euclid must add three stones to the stack in his move. Thanks to that Pythagoras can collect all 4 stones in his move and thus win.