Paweł i Gaweł 2

Time limit1sMemory limit128 MB

Summary

Two players alternately remove stones from the leftmost or rightmost pile, and you decide who takes the last stone when both play their best.

Level: Hard8 of 10
Topics: Game theory, Dynamic programming
Solved: No attempts yet

Problem

After settling who takes the upper floor of their new house, Paweł and Gaweł decide to play another game, this time for the right to use the attic.

They place $N$ piles in a row on the table, each holding at least $1$ stone. Stones within a pile are indistinguishable. Starting with Paweł, the players move alternately. On a move, a player chooses either the leftmost remaining pile or the rightmost remaining pile and removes any number of stones (at least $1$ ) from it.

The player who removes the last stone wins, and both players play optimally. Who earns the right to use the attic?

Input

The first line contains the number of test cases $Z$ ( $1 \le Z \le 10$ ).

Each test case spans two lines. The first line holds the number of piles $N$ , and the second line holds the stone counts $A_i$ of the piles from left to right, separated by spaces. ( $1 \le N \le 200$ , $1 \le A_i \le 200$ )

Output

For each test case, print the answer on its own line: P if Paweł can force a win no matter how Gaweł plays, otherwise G.

Examples8

Example 1
Input
```
2
3
2 5 3
4
7 7 7 7
```
Expected output
```
P
G
```
Example 2
Input
```
1
1
1
```
Expected output
```
P
```
Example 3
Input
```
1
2
5 5
```
Expected output
```
G
```
Example 4
Input
```
1
2
3 8
```
Expected output
```
P
```
Example 5
Input
```
1
5
1 1 1 1 1
```
Expected output
```
P
```
Example 6
Input
```
1
4
1 1 1 1
```
Expected output
```
G
```
Example 7
Input
```
2
3
1 2 1
3
2 1 2
```
Expected output
```
G
G
```
Example 8
Input
```
1
3
2 5 3
```
Expected output
```
P
```