There are N marbles lying on a table. There are two players. On each move, a player can take:
1 or 2 marbles if N is divisible by 3.
1 or 3 marbles if N - 1 is divisible by 3.
1, 2 or 3 marbles if N - 2 is divisible by 3.Player 1 makes the first move. Each move can be made only if there are enough marbles to take. The player who cannot make a move loses the game. Find the winner if both players play optimally.
For each test case the answer is 1 or 2 - corresponding to first and second player respectively, who will win the game.Print the final answer as the sum of outputs for each N.
ExamplesFor N=2, output is 1
When N=2, first player takes both the marbles. Hence no marbles are left for second player. So first player wins
Kunal Desai : 7715051136
Neelraj Patil : 9930671144