MINVSMIN - Minions v/s Minions

The minions have been recently troubling Gru for buying them bananas. Gru sets up an N*N banana field, where the cells that contain bananas are denoted by b, the cells which contains bombs are denoted by B. Two pack of minions are allowed to enter the field at a time from entry points marked in the fields as X and Y. We all know how childish they are and competitive they can be. Each pack from a position can divide themselves into four directions – up, down, left, right (they don’t cross the boundaries of the field.) They are smart enough to avoid the bombs. Whichever minion pack reaches a cell first gets to keep the banana, but if both packs reach a cell at the same time they smash the banana and do not allow each other to move ahead from that point. However, if member of the same pack meet at a cell they reunite and move ahead on their hunt for bananas. Remember though Gru has strictly asked them not to travel through already visited cells because of the dropped off banana peels (they can be messy at times too!)

Gru has to figure out which pack acquired more bananas. Gru dozes off in the middle of the banana battle. Please help him to declare the winner – Pack 1 or Pack 2.

PS: You can assume each pack contains infinite number of minions, so the pack never runs out of individuals while dividing themselves in the four directions.

Input

The first line contains number of test cases T. Following test case description contains N and N*N banana field’s description.

1 <= T <= 30

1 <= N <= 1000

Output

You need to print “Pack 1” if Pack 1 wins and “Pack 2” if Pack 2 wins and “Gru gets to keep all bananas!” if there is a draw.

Example

Input:
2
3
bXb
bBb
YBb
5
BBBBB
XbbbY
BBBBB
Bbbbb
bbbbb

Output:
Pack 1
Gru gets to keep all bananas!

Added by:stardex
Date:2017-08-27
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2017-08-29 19:15:40
stupid warning maybe.. but be careful while using scanf.. caused two WA due to a silly mistake in buffer and flush :(

Last edit: 2017-08-29 19:15:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.