HUBULLU - Hubulullu

no tags 

After duelling in quake (a multiplayer game), Airborne and Pagfloyd decide do test themselves out in another game called Hubulullu. The rules of the game are as follows:

N wooden pieces (marked with numbers 1 to N) are placed in a transparent bottle. On his turn the first player takes out some piece (numbered x) and all the pieces numbered by divisors of x that are present in the transparent bottle. The second player picks another number and removes it and its divisors as well. Play continues in an alternating fashion until all pieces have been removed from the bottle. The player who removes the last piece from the bottle wins the game.

Both players play optimally. Given N (the number of wooden pieces in the transparent bottle initially) and the name of the player who starts the game, determine the winner.

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

Each test case consists of a single line containing two integers separated by a single space. The first integer is N (1 <= N <= 2000000000), indicating the number of pieces, and the second integer indicates the player who starts - "0" means Airborne starts the game and "1" means Pagfloyd starts the game (quotes for clarity).

Output

For each test case output one line containing either "Airborne wins." or "Pagfloyd wins."

For each N, it's possible to determine a winner if both players play optimally.

Example

Input:
1
1 0

Output:
Airborne wins.

hide comments
raghvendra_2: 2016-12-11 19:39:16

problem that can easily threatened you initially

Last edit: 2016-12-11 19:39:52
tni_mdixit: 2016-12-08 19:26:21

what was that? :P i was like brain fucked for half an hour and then i came up with the logic.

spartax: 2016-12-07 18:41:26

LOL !!

vivace: 2016-10-28 16:15:27

The logic is way too good . Superlike (y)

angel_of_death: 2016-10-22 13:11:44

Lol I thought there was no way my solution would get accepted since it was so simple. But it did.

sayedathar11: 2016-09-21 08:33:24

After this problem try tweedle dee and dum problem from codechef you will get more insight to parity and other concepts it is similar requires a deep thinking

sayedathar11: 2016-09-21 08:33:23

After this problem try tweedle dee and dum problem from codechef you will get more insight to parity and other concepts it is similar requires a deep thinking

harshgupta007: 2016-08-24 08:16:54

Easy. AC in one go

luc815689327: 2016-08-16 14:00:54

At first I find it weird that here is no test case, until the logic blows my mind.....orz

code1monkey1: 2016-06-15 13:31:31

"optimally " word stole the show :P


Added by:Matthew Reeder
Date:2006-10-29
Time limit:1.787s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006