You are given a grid of size N×N that has the following specifications:
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≤T≤10
1≤N≤1000
1≤K≤N∗N
Total Thieves = 5
Number of thieves reachable by policemen in Row 1 = 1
Number of thieves reachable by policemen in Row 2 = 2
Number of thieves reachable by policemen in Row 3 = 1
However, one policeman can catch at most 1 thief. Hence, in Row 2, only 1 thief is catchable.
Therefore, the 3 thieves can be caught.