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

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 \)