eolymp
bolt
Try our new interface for solving problems
Problems

Гра в закреслення

Гра в закреслення

Time limit 1 second
Memory limit 64 MiB

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

Input data

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

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

1 ≤ K ≤ N ≤ 100

Output data

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

Examples

Input example #1
3
4 2
OOOO
5 2
OOOOO
7 2
OXXOXXO
Output example #1
1
2
0