Ігри з шишечками
- Мишко, а навіщо ти кожен раз приносиш з лісу разом з гілочками так багато шишечок? Адже для викладування знаків арифметичних дій тобі їх вистачило б у межах десятка, ну максимум двох…
- А ми з тобою, Маша, цими шишечками будемо в ігри грати до весни, а весною шишечки посадимо, і з них виростуть нові ялинки.
- А що за гра?
- Значить, правила такі: я розкладаю N кучок з шишечками, у кожній купці – як повезе, тобто скільки зумію за один раз з мішечка на купку висипати. Далі будемо брати шишечки по черзі, і ти при цьому будеш завжди ходити першою. За один хід можна взяти довільну кількість шишечок не менше ніж з однієї, але не більше ніж з K купок. Хто забере останню шишечку – той і виграв.
- Ух ти, як цікаво! Давай Мишко швидше розкладай – пограємо.
Ваше завдання дуже просте: визначити, хто з них виграє у черговій грі, якщо відомо, що і Маша і Мишко дотримуються у цій грі оптимальної виграшної стратегії.
Вхідні дані
У першому рядку задано натуральне число T - кількість ігр між Машою і Мишком – не більше 100. Далі у T пар рядках описано самі ігрові положення перед початком чергової гри: у першому рядку кожної пари задано натуральні N (1 ≤ N ≤ 10000) і K, а у другому через пропуск описано кількість шишечок S_i (0 ≤ S_i ≤ 2147483647) у кожній купці.
Вихідні дані
Для кожного тестового випадку у окремому рядку виведіть повідомлення "Masha wins", якщо виграє Маша або "Misha wins", якщо, відповідно, виграє хитрий і мудрий ведмідь (адже не просто так він поступався правом першого ходу Маші).