Strange Calculator
Misha, tired of Masha's games with cones, decided to give her a calculator, hoping she would leave him alone. However, Masha quickly invented a new game using the calculator and invited Misha to play. The game is simple: Masha starts by setting the calculator display to the number 1, while Misha writes a natural number N in the sand. They take turns, with Masha always going first. During each turn, a player can multiply the current number on the calculator by any natural number between 2 and 9. The winner is the first player to display a number on the calculator that is greater than or equal to the number Misha wrote.
Your task is to write a program that determines the winner of this game, assuming both players use the optimal strategy.
Input
The input consists of multiple test cases, each on a separate line, containing a single natural number not exceeding 4294967295.
Output
For each test case, output "Masha wins." on a separate line if Masha wins, or "Misha wins." if Misha wins.