В Змійляндії живуть змії та мангусти. Вони розташовані в ряд і інформація про їх розташування задається рядком \(S\). Так, \(і\)-й символ цього рядка дорівнює або \(s\), якщо на \(і\)-му місці стоїть змія або \(m\), якщо на \(і\)-му місці стоїть мангуст.

Змії та мангусти не люблять одне одного. Завтра у Змійляндії відбудуться вибори. Кожен її житель буде голосувати за свій вид( тобто, змії за змій, а мангусти — за мангустів). Переможе той вид, голосів за який буде строго більше, як за вид противників.

Мангусти вирішили піти на обман для того, щоб виграти вибори: кожен мангуст перед початком голосування з’їсть не більше одного із своїх змій сусідів (якщо вони є) так, щоб число змій стало мінімально можливим. Сусідами вважаються тварини, які знаходять безпосередньо зліва або справа.

Складіть програму, яка визначить, який вид виграє вибори після обманних дій мангустів. Виведіть:

• “snakes”, якщо це будуть змії

• "mongooses", як виграєть мангусти

• "tie", якщо змії та мангусти наберуть рівну кількість голосів.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(Т\) \((1 ≤ T ≤ 100)\) — кількість тестів.

У наступному рядку міститься один текстовий рядок \(S\) \((1 ≤ |S| ≤ 100)\), який описує розташування змій та мангустів символами “\(s\)” та “\(m\)” відповідно.

Формат вихідних даних

Для кожного тесту вивести в окремому рядку переможця виборів відповідно до умови задачі.

Приклад вхідних даних

4
sm
ssm
sms
ssmmmssss

Приклад вихідних даних

mongooses
tie
tie
snakes