Задачи
Странный калькулятор
Странный калькулятор
Так как Маша уже "достала" Мишу своими играми с шишечками, Миша решил подарить ей калькулятор, думая (такой большой - а странный... :) ), что после этого Маша от него отстанет. Однако смышлёная Маша тут же придумала игру с калькулятором и предложила Мише опять поиграть с ней. Суть игры в следующем. Перед началом игры Маша устанавливает на экране калькулятора число \textbf{1}, а Миша записывает на песке натуральное число \textbf{N}. Ходы, как и положено в равноправных играх они делают по очереди, но Маша всегда ходит первой. За один ход разрешается умножить результат, отображаемый на экране калькулятора, на любое натуральное число большее \textbf{1} и меньшее \textbf{10}. Побеждает тот, кто первый сумеет добится отображения на экране калькулятора числа, не меньшего, чем то, что записал Миша.
Вам предстоит написать программу, которая определяет, кто побеждает в этой странной игре, если и Миша и Маша всегда придерживаются оптимальной стратегии.
\InputFile
Входные данные состоят из некоторого набора тестовых случаев, каждый из которых размещён в отдельной строке и содержит единственное натуральное число, не превышающее \textbf{4294967295}.
\OutputFile
Для каждого тестового случая в отдельной строке вывести "\textbf{Masha wins.}", если выиграет Маша, или "\textbf{Misha wins.}", если выиграет Миша.
Входные данные #1
162 17 34012226
Выходные данные #1
Masha wins. Misha wins. Masha wins.