Maximum KxK Submatrix Sum

You are given an N x N matrix of integers and an integer k. Your task is to find the maximum sum of any contiguous submatrix of size k x k located within the matrix.

Mathematically, if the matrix is represented as \(A\) with indices from 1 to \(N\), then for any valid submatrix starting at \(A_{a,b}\), the sum \(S\) of the submatrix is given by:

\[ S = \sum_{i=a}^{a+k-1} \sum_{j=b}^{b+k-1} A_{i,j} \]

Your goal is to determine the maximum such \(S\) over all possible \(a, b\) such that the \(k \times k\) submatrix lies entirely within the matrix.

inputFormat

The input is read from standard input and has the following format:

• The first line contains a single integer \(T\), the number of test cases.
• For each test case:
  • The first line contains two space-separated integers \(N\) and \(k\) where \(N\) is the size of the matrix and \(k\) is the size of the submatrix.
  • Then follow \(N\) lines, each containing \(N\) space-separated integers representing the rows of the matrix.

outputFormat

For each test case, output a single integer on a new line — the maximum sum of any contiguous \(k \times k\) submatrix.

## sample

1
4 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

4

</p>