Cross-out Game#7359
A strip of paper is divided into cells. Two players take turns choosing and crossing out exactly consecutive empty cells. The player who makes the last valid move wins. Both players use optimal strategies. Given the current state of the game, determine which player will win.
The first line contains a single integer (1 \le T \le 100): the number of test cases.
Each test consists of two lines:
The first line contains two integers and (1 \le K \le N \le 100).
The second line contains a string of characters, where each character is either the uppercase letter (representing an empty cell) or the uppercase letter (representing a crossed-out cell).
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.
Example 1