The Game of Two Elves#10265
Saint Nicholas has devised an intriguing game for his elf friends, Marko and Sava. He has drawn a sequence of bits for them to play with.
The game proceeds in turns, starting with Marko. During a turn, an elf must select an index such that 1 \leq i \leq n and the -th bit of the sequence is . The elf then flips all bits from position to (i.e., bits that are become , and bits that are become ). The elf who cannot make a move loses the game.
Both Marko and Sava are very clever and will play the game optimally. Your task is to determine the winner for each of the initial sequences provided by Saint Nicholas. Note that all games are independent of each other.
The first line contains a single integer (1 \leq t \leq 50), representing the number of games.
Each game is described by two lines:
The first line contains a single integer (1 \leq n \leq 10^4), the length of the bit sequence.
The second line contains a sequence of bits.
For each game, output Marko if Marko wins, or Sava if Sava wins.
Example 1
In the first example, after Marko's only possible move, the sequence becomes . Sava can then change it to in one move and win.
In the second and third examples, Marko wins after making just one move.
This problem includes two test cases with non-zero scores. One test case is worth points and has additional constraints: t = 16, n = 4.