eolymp
bolt
Try our new interface for solving problems
Problems

Странный калькулятор

Странный калькулятор

Time limit 1 second
Memory limit 32 MiB

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

Вам предстоит написать программу, которая определяет, кто побеждает в этой странной игре, если и Миша и Маша всегда придерживаются оптимальной стратегии.

Input data

Входные данные состоят из некоторого набора тестовых случаев, каждый из которых размещён в отдельной строке и содержит единственное натуральное число, не превышающее 4294967295.

Output data

Для каждого тестового случая в отдельной строке вывести "Masha wins.", если выиграет Маша, или "Misha wins.", если выиграет Миша.

Examples

Input example #1
162
17
34012226
Output example #1
Masha wins.
Misha wins.
Masha wins.
Source II этап Всеукраинской олимпиады школьников 2012-2013, г. Бердичев