Гра стратегії#1297
— Лисе, навіщо ти зібрав стільки пелюсток троянд?
— З ними, Маленький принце, ми гратимемо в гру, яка навчить тебе передбачати кроки вперед. Це одна з найважливіших мудростей: вміти бачити не лише сьогодення, а й майбутнє.
— А як грати?
— Правила прості, але їх розуміння вимагає справжньої мудрості: я розкладу купок пелюсток. Потім ми почергово забиратимемо їх, і ти ходитимеш першим. За один хід гравець може взяти будь-яку кількість пелюсток щонайменше з однієї і щонайбільше з купок. Той, хто забере останню пелюстку, перемагає. Але пам'ятай: важливо не тільки те, що ти бачиш зараз, а й те, що станеться після твого ходу.
— Це справді вимагає думання наперед...
— Саме так. Справжня стратегія — це вміння бачити те, що ще не сталося.
Ваше завдання: визначити, хто виграє кожну гру, якщо обидва гравці — і Маленький принц, і Лис — гратимуть найкраще з можливих варіантів.
Перший рядок містить одне додатне ціле число — кількість ігор (1 \leq T \leq 100). Кожна з наступних пар рядків описує початкову позицію для гри: перший рядок містить два додатних числа (1 \leq N \leq 10000) і , другий рядок містить чисел S_i (0 \leq S_i \leq 2147483647), де S_i — кількість пелюсток у кожній купці.
Для кожного тесту виведіть у окремому рядку "Masha wins", якщо виграє Маленький принц (який ходить першим), або "Misha wins", якщо виграє Лис.
Приклад 1