Игра в зачеркивание

Полоса бумаги разделена на N клеток. Два игрока по очереди выбирают и зачеркивают ровно K пустых смежных клеток. Побеждает тот, кто сделает последний ход. Оба игрока играют оптимально. Вам дана текущая ситуация игры, и нужно определить, кто выиграет.

Входные данные

Первая строка содержит одно число T — количество тестов.

Далее следуют T наборов данных, каждый из которых состоит из двух строк. Первая строка содержит два числа N и K. Вторая строка содержит строку из N символов, где латинская заглавная O обозначает пустую клетку, а латинская заглавная X — зачеркнутую клетку.

1 ≤ K ≤ N ≤ 100

Выходные данные

Выведите одно число: 1, если выиграет первый игрок; 2, если выиграет второй игрок; 0, если ход невозможен.

Примеры