Find an All-Ones Square Submatrix

You are given a binary matrix of size n × m and an integer k. Your task is to determine whether there exists a contiguous k × k submatrix that contains only 1's. In other words, check if there is any submatrix of size $k\times k$ where every element is equal to 1.

Note: A submatrix is defined as a block of consecutive rows and columns.

inputFormat

The first line of input contains an integer T indicating the number of test cases. Each test case is described as follows:

• The first line contains three space-separated integers n, m, and k where n and m denote the number of rows and columns of the matrix, and k is the size of the submatrix to be checked.
• The next n lines each contain m integers (either 0 or 1) representing the matrix.

All input should be read from standard input (stdin).

outputFormat

For each test case, output a single line containing YES if there exists a k × k submatrix entirely composed of 1's, otherwise output NO. The output for each test case should be written to standard output (stdout), with each result on a new line.

1
3 3 2
1 1 1
1 1 1
1 1 1

YES