Гра в закреслювання#7359
Смуга паперу розділена на клітин. Двоє гравців по черзі вибирають і закреслюють рівно порожніх суміжних клітин. Перемагає той, хто зробить останній хід. Обидва гравці дотримуються оптимальної стратегії. Дано поточний стан гри, визначте, хто переможе.
Перший рядок містить одне число (1 \le T \le 100): кількість тестів.
Кожен тест складається з двох рядків:
Перший рядок містить два числа і (1 \le K \le N \le 100).
Другий рядок містить рядок із символів, де кожен символ — це латинська велика літера (порожня клітина) або (закреслена клітина).
Для кожного тесту виведіть одне число:
1, якщо переможе перший гравець;
2, якщо переможе другий гравець;
0, якщо жодного ходу зробити неможливо.
Приклад 1