Paweł i Gaweł, po ustaleniu kto zajmuje górne piętro ich nowego domu, postanowili zagrać w kolejną grę - tym razem o prawo do użytkowania strychu.</p>

Nasi bohaterowie ustawili na stole w rzędzie N stosów z niezerową liczbą nierozróżnialnych kamieni. Następnie na zmianę, począwszy od Pawła, wykonywali ruchy polegające na zdjęciu dowolnej niezerowej liczby kamieni z pierwszego niepustego stosu od lewej lub prawej.

Jeśli wygrywa gracz, który zdejmie ostatni kamień i obaj nie popełniają błędów, to kto z nich zdobędzie prawo do użytkowania strychu?

입력 형식

W pierwszej linii znajduje się jedna liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych.</p>

Każdy zestaw testowy składa się z dwóch linii. W pierwszej znajduje się jedna liczba naturalna N - oznaczająca liczbę stosów. W kolejnej linii następuje N liczb całkowitych A_i - liczb kamieni na kolejnych stosach od lewej do prawej. (1 <= N <= 200, 1 <= A_i <= 200)

출력 형식

Dla każdego zestawu testowego należy w osobnej linii wypisać literę P jeśli niezależnie od ruchów Gawła Paweł jest w stanie wygrać. W przeciwnym razie należy wypisać G.

예제 입력

2
3
2 5 3
4
7 7 7 7

예제 출력

P
G