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