The Game of Strategy#1297
— Fox, why have you gathered so many rose petals?
— With them, Little Prince, we will play a game that will teach you to see steps ahead. This is one of the most important wisdoms: to be able to see not only the present, but also the future.
— How do we play?
— The rules are simple, but understanding them requires true wisdom: I will arrange piles of petals. Then we will take turns collecting them, and you will go first. On each turn, a player can take any number of petals from at least one and at most piles. The one who takes the last petal wins. But remember: what matters is not only what you see now, but also what will happen after your move.
— This really requires thinking ahead...
— Exactly so. True strategy is the ability to see what has not yet happened.
Your task: determine who will win each game if both players — both the Little Prince and the Fox — play in the best possible way.
The first line contains a positive integer , the number of games (1 \leq T \leq 100). Each of the following pairs of lines describes the starting position for a game: the first line contains the positive integers (1 \leq N \leq 10000) and , and the second line contains numbers S_i (0 \leq S_i \leq 2147483647), where S_i is the number of petals in each pile.
For each test case, print on a separate line "Masha wins" if the Little Prince wins (who goes first), or "Misha wins" if the Fox wins.
Example 1