NPC2014A - I Ken Bit Yu


On a hot day in Surabaya, Puguh is bored. He then declares himself as "the bestest player in teh wurld", challenging his friend named Joke to play a game. Here is the description of the game:

  • There are N piles of coins and each pile contains Xi coins (i=1 to N).
  • Each player alternately takes turn.
  • On each turn, a player must take a number of coin from any pile. The number of coin taken must be a divisor of the current pile size and must be less than the current pile size. For example, if Puguh chooses a pile with 6 coins, then he may take 1, 2, or 3 coins from that pile.
  • The first player that can't take any coin on his turn loses.

Puguh and Joke will play optimally. If Puguh is the first player to move, predict the winner of this game.

 

Input

Input starts with a number T, the number of test cases. For each test case, the first line contains a number N. The next line contains N numbers Xi, number of coins on the i-th pile.

Output

For each case, output a line. If Puguh won the game, output "Puguh is the bestest player in teh wurld" and if Joke won the game, output  "Joke is the bestest player in teh wurld".

Sample Input

1 
1
6

Sample Output

Puguh is the bestest player in teh wurld

Constraint

  • 1 ≤ T ≤ 50
  • 0 ≤ N ≤ 100000
  • 0 ≤ Xi ≤ 1000000000

Input file is huge, use faster I/O (scanf for C)


hide comments
rajat_kumar: 2016-10-23 12:23:58

nim problems are the bestest in teh wurld,:P

thenamesake: 2015-06-25 21:31:39

Great Problem mind the n=0 , x=0

Last edit: 2015-06-25 21:31:56
Pranjal Shankhdhar: 2015-05-16 12:25:34

Last edit: 2015-05-16 13:58:59
Pranjal Shankhdhar: 2015-05-16 12:23:56

RIP English :P

Akhilesh Anandh: 2014-10-31 11:00:35

Awesome problem :)

Aditya Pande: 2014-10-27 10:33:48

Nice problem
Learnt a lot from this problem :)

@surayans tiwari: 0 is a terminal i.e losing position

surayans tiwari(http://bit.ly/1EPzcpv): 2014-10-24 00:16:39

what for 0?

Jacob Plachta: 2014-10-24 00:16:39

It's worth clarifying that the number of coins you take must be a divisor of the current pile size (as opposed to the original Xi value), and that there are of course no valid moves for an empty pile.


Andy: updated the description, thanks!

Last edit: 2014-10-22 09:33:29

Added by:Andy
Date:2014-10-21
Time limit:0.5s-0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NPC Schematics 2014