\textit{- Миша, а зачем ты каждый раз приносишь из лесу вместе с веточками так много шишечек? Ведь для выкладывания знаков арифметических действий тебе их хватило бы в пределах десятка, ну максимум двух…} \textit{- А мы с тобой, Маша, этими шишечками будем в игры играть до весны, а весной шишечки посадим, и из них вырастут новые ёлочки.} \textit{- А что за игра?} \textit{- Значит, правила такие: я раскладываю }\textit{\textbf{N}}\textit{ кучек с шишечками, в каждой кучке -- как повезёт, т.е. сколько сумею за один раз из мешочка на кучку высыпать. Далее будем брать шишечки по очереди, и ты при этом будешь всегда ходить первой. За один ход можно взять произвольное число шишечек из не менее одной, но не более чем из }\textit{\textbf{K}}\textit{ кучек. Кто заберёт последнюю шишечку -- тот и выиграл.} \textit{- Ух ты, как интересно! Давай быстрее Миша раскладывай -- поиграем.} Ваша задача очень проста: определить, кто из них выиграет в очередной игре, если известно, что и Маша и Миша придерживаются в этой игре оптимальной выигрышной стратегии. \InputFile В первой строке задано натуральное число \textbf{T} - количество игр между Машей и Мишей -- не более \textbf{100}. Далее в \textbf{T} пар строк описаны сами игровые положения перед началом очередной игры: в первой строке каждой пары заданы натуральные \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10000}) и \textbf{K}, а во второй через пробел описано количество шишечек \textbf{S_i} (\textbf{0} ≤ \textbf{S_i} ≤ \textbf{2147483647}) в каждой кучке. \OutputFile Для каждого тестового случая в отдельной строке выведите сообщение "\textbf{Masha wins}", если выиграет Маша или "\textbf{Misha wins}", если, соответственно, выиграет хитрый и мудрый медведь (ведь не просто так он уступал право первого хода Маше).