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

Вхідні дані

У першому рядку містяться одне число Т, кількість тестів.

Далі іде T записів по 2 рядка коден, перший з яких містят числа N і K, у другому рядку N символів: латинська велика O - пуста клітинка, латинська велика X - закреслена клітинка.

1 ≤ K ≤ N ≤ 100

Вихідні дані

Вивести одне число: *1 *- якщо виграє той, хто зробить хід першим; 2 - якщо виграє другий; 0 - якщо хід зробити неможливо.