Playing with knobs
- Misha, why did you every time bring from the forest so many branches with knobs? After all, for putting some signs of arithmetic operations it would be enough ten, or maximum twenty of them...
- With these knobs, Masha, we shall play the game until spring, and in spring we shall plant them to grow the new fur-trees.
- And what is the game?
- Hence, the rules are follows: I lay out N knobs in piles, in each pile - as lucky I can pour out of the bag. Next, we shall take the knobs in turns, and in each game you'll always go first. In each move the player can take any number of knobs at least from one but not more than from K piles. The player who takes the last knob is declared to be a winner.
- Wow, how interesting! Come quickly Misha lay out - let's play.
Your task is simple: to determine who of them will win the game, if you know that Masha and Misha follow the best winning strategy in this game.
Input
The first line contains a positive integer T - the number of games between Masha and Misha, no more than 100. Next T pairs of strings describe the playing positions before the start of each game: in the first line the natural N (1 ≤ N ≤ 10000) and K are given, and the second line describes the number of knobs S_i (0 ≤ S_i ≤ 2147483647) in each pile.
Output
For each test case in a separate line print the message "Masha wins", if Masha wins or "Misha wins", if, respectively, wins a cunning and wise bear (after all, not just because he gives the right of the first stroke to Masha).