Nim Game II

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game. Your task is to find out who wins if both players play optimally. Input The first input line contains an integer t: the number of tests. After this, t test cases are described: The first line contai