You are given a grid of size \( N \times N\) that has the following specifications:

• Each cell in the grid contains either a policeman or a thief.
• A policeman can only catch a thief if both of them are in the same row.
• Each policeman can only catch one thief.
• A policeman cannot catch a thief who is more than K units away from the policeman.

Write a program to find the maximum number of thieves that can be caught in the grid.

Input format

• First line: T (number of test cases)
  For each test case
• First line: Two space-separated integers N and K
• Next N lines: N space-separated characters (denoting each cell in the grid)

Output format

For each test case, print the maximum number of thieves that can be caught in the grid.

Constraints

\(1 \le T \le 10 \)
\( 1 \le N \le 1000 \)
\( 1 \le K \le N*N \)