Counting (L, L)-Square Matrices with Equal Sums

You are given a grid with N rows and M columns. Your task is to count the number of L × L submatrices (square sub-grids with side length L) for which the sum of every row is equal and the sum of every column is equal. In other words, in each valid submatrix, all the row sums must be identical, and all the column sums must be identical (they do not necessarily have to be the same as each other).

Input Format: The input is read from standard input and begins with an integer T representing the number of test cases. For each test case, the first line contains three space-separated integers: N, M, and L. This is followed by N lines, each containing M space-separated integers representing the grid.

Output Format: For each test case, output a single integer on a new line representing the count of valid L × L submatrices.

Note: The row sums and column sums are computed separately for each L × L submatrix.

inputFormat

The first line of input contains an integer T indicating the number of test cases. For each test case, the first line contains three integers N, M and L — the number of rows, columns, and the side length of the square submatrix respectively. The next N lines each contain M integers representing the grid.

outputFormat

For each test case, output a single integer on a new line representing the number of L × L submatrices for which all row sums are equal and all column sums are equal.

## sample

2
3 3 2
1 2 3
4 5 6
7 8 9
4 4 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

0
4

</p>