There are 2 people who play a game. The game is as follows:

The are P sticks, each of length Q meters in length. The player play in turns. For each move a player choses a stick and splits it into 2 or more equal parts, each having an integer length greater than or equal to S meters. Each resulting part is also a stick. The player who can't make a move loses and the other player wins.

If both the players play optimally, determine the winner, given the values of P, Q and S.

For example : 2

1 15 4

4 9 5

Answer:

Player 1

Player 2

Constrains: 1 <= T <= 10, the number of test cases

1 <= P, Q, S <= {10}⁹.

My approach till now: I was trying to solve this problem using grundy numbers. If the xor of grundy numbers of all piles is 0, player 2 is winner else player 1 is winner. Since all sticks are of same length, P = even number implies, player 2 is always the winner. When P = odd number, then if the grundy number of stick is 0, then player 2 is winner else player 1 is winner. The grundy is 0 only when all the proper divisors (i.e. except 1 and number itself) of the stick length are less than S.

Could anyone please verify whether my approach is correct or not?

Any help would be appreciated.