Cross-out Game

A strip of paper is divided into N cells. Two players take turns choosing and crossing out exactly K consecutive empty cells. The player who makes the last valid move wins. Both players use optimal strategies. Given the current game state, determine which player will win.

Input

The first line contains a single integer T, the number of test cases.

Each test case consists of two lines:

• The first line contains two integers, N and K.

• The second line contains a string of N characters, where each character is either an uppercase O (representing an empty cell) or an uppercase X (representing a crossed-out cell).

Constraints:

• 1 ≤ K ≤ N ≤ 100

Output

For each test case, output a single integer:

• 1 if the first player will win,

• 2 if the second player will win,

• 0 if no moves can be made.

Examples