Гра двох ельфів#10265

Гра двох ельфів

1 секунда

256 мегабайтів

Дуже легка

Святий Миколай вигадав дуже цікаву гру для своїх друзів-ельфів: Марка та Сави. Святий Миколай намалював послідовність з $n$ бітів.

Гравці ходитимуть по черзі, першим ходитиме Марко. На своєму ході ельф повинен вибрати певний індекс $i$ такий, що $1 \leq i \leq n$ 1 \le i \le n та $i$ -ий біт послідовності рівний $1$ , після чого він змінить всі біти з номерами $1, 2, \dots, i$ 1, 2, \dots, i (тобто, біти зі значенням $0$ отримають значення $1$ , а біти зі значенням $1$ отримають значення $0$ ). Програє той гравець, який не зможе зробити свій хід.

Відомо, що Марко та Сава — дуже розумні ельфи, та гратимуть в описану гру оптимально. Допоможіть дізнатись переможців ігор для $t$ початкових послідовностей Святого Миколая. Зауважте, що всі $t$ ігор є незалежними.

Вхідні дані

Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 50$ 1 \le t \le 50).

Кожна початкова послідовність Святого Миколая задається у двох рядках:

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4).

Другий рядок містить послідовність бітів Святого Миколая довжиною $n$ .

Вихідні дані

Виведіть переможців $t$ ігор. Для кожної гри виведіть Marko, якщо переможе Марко, або Sava, якщо переможе Сава.

Приклади

Приклад 1

Примітка

У першому прикладі після єдиного можливого ходу Марко послідовність матиме вигляд $110$ . Після цього Сава зможе перетворити її у $000$ за один хід і виграти.

У другому і третьому прикладах Марко завжди робить один хід і виграє.

Оцінювання

У цій задачі лише два тести, що оцінюються в ненульову кількість балів.

Один з них оцінюється у $25$ балів та для нього виконуються додаткові обмеження: $t = 16$ t = 16, $n = 4$ n = 4.