Дивний калькулятор

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

Ваше завдання — написати програму, яка визначає, хто переможе у цій дивній грі, якщо і Маша, і Міша завжди дотримуються оптимальної стратегії.