TAKE4 - Take Away Game

no tags 

Two players play the following game:
a) A number N is chosen
b) players move alternately starting from player1
c) On his turn, a player may subtract either 1, 2 , 3 .. or M ( M <= N ) from N.
d) The player to make N equal to 0, wins.
e) 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, determine who wins the game.
 
Input:
First line consists of the number of test cases T (T <= 1000). Each of the next T lines consists of two integers, the numbers N and M (1 <= N <= 2000).
 
Output:
You must ouput 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:
player1 wins
player2 wins



Added by:Varun Jalan
Date:2010-09-06
Time limit:1.094s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC VB.NET