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