Two players play the following game:

• A number N is chosen.
• Players move alternately starting from player 1.
• On his turn, a player may subtract either 1, 2, 3 .. M from N.
• The player to make N equal to 0, wins.
• Both play optimally. That is, if there is a move which makes a player win, he is sure to find it.

Given the starting value N and M, determine who wins the game.

Input

First line consists of the number of test cases T (T <= 1000). Each of the next T lines contains two integers, the numbers N and M (1 <= N <= 2000, M <= N).>/p>

Output

You must output T lines. Output "player 1 wins" (without quotes) if the first player wins, else output "player 2 wins".

Example

Input:
2
4 4
2 1

Output:
player 1 wins
player 2 wins