Consecutive Accessible Seats

You are given a square seating map, represented as a matrix of characters. Each cell in the matrix is either 'A' (accessible) or 'N' (not accessible). The task is to determine whether there exists at least one row or one column in the matrix that contains at least m consecutive accessible seats.

Formally, given an n×n seating map and an integer m, your goal is to check if there exists any row or column in which the string AAAA...A (m times) appears as a contiguous substring. If such a sequence exists, output YES, otherwise output NO.

You may assume that the input matrix is square. All indices are 0-indexed and the cities of the seats are arranged in the order as given in the input.

The problem can be summarized by the following condition using \(\LaTeX\):

[ \exists \text{ row or column } X : \text{``A''}_{m} \subseteq X ]

where \(\text{``A''}_{m}\) denotes a string of m consecutive 'A's.

inputFormat

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

• The first line contains two integers, n and m, where n is the size of the square seating map and m is the minimum number of consecutive accessible seats required.
• The following n lines each contain a string of length n consisting of the characters 'A' and 'N' which represent accessible and non-accessible seats respectively.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing either YES or NO. YES is printed if there exists a row or column with at least m consecutive 'A' characters; otherwise, print NO. Output is written to standard output (stdout).

## sample

5
3 2
AAN
NAA
NNA
3 2
ANN
NAN
NNA
3 3
AAA
NAN
AAA
2 2
NN
NN
4 2
AAAA
NNAA
ANNN
AANN

YES
NO
YES
NO
YES

</p>