Tic-Tac-Toe used to be Chef's favourite game during his childhood. Reminiscing in his childhood memories, he decided to create his own "Tic-Tac-Toe", with rules being similar to the original Tic-Tac-Toe, other than the fact that it is played on an NxN board.

The game is played between two players taking turns. First player puts an 'X' in an empty cell of the board, then the second player puts an 'O' in some other free cell. If the first player has K continuous X's or the second player has K continuous O's in row, column or diagonal, then he wins.

Chef started playing this new "Tic-Tac-Toe" with his assistant, beginning as the first player himself (that is, Chef plays 'X's). Currently, the game is ongoign, and it's Chef's turn. However, he needs to leave soon to begin tonight's dinner preparations, and has time to play only one more move. If he can win in one move, output "YES", otherwise output "NO" (without quotes). It is guaranteed that no player has already completed the winning criterion before this turn, and that it's a valid "Tic-Tac-Toe" game.

-----Input-----
The first line of input contains one integer T denoting the number of testcases. First line of each testcase contains two integers N and K, next N lines contains N characters each. Each character is either an 'X' denoting that the first player used this cell, an 'O' meaning that the second player used this cell, or a '.' (a period) representing a free cell.

-----Output-----
For each testcase, output, in a single line, "YES" if Chef can win in one move, or "NO" otherwise.

-----Constraints-----
- 1 ≤ T ≤ 100
- 3 ≤ N ≤ 20
- 1 ≤ K ≤ N

-----Example-----
Input:
3
3 3
XOX
O.O
XOX
3 1
...
...
...
3 2
...
...
...

Output:
YES
YES
NO

Input:
1
4 4
XOXO
OX..
XO..
OXOX

Output:
YES

-----Subtasks-----
- Subtask 1:  K  = 1. Points - 10
- Subtask 2:  N  =  K  = 3. Points - 30
- Subtask 3: Original constraints. Points - 60

-----Explanation-----
Test #1:

In first testcase, put 'X' in (2, 2), in second we can put 'X' in any cell and win. 
Test #2:

If you put an 'X' in (3, 3), there will be four 'X's on the main diagonal (1, 1) - (2, 2) - (3, 3) - (4, 4).

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def f(n, k):
	s = []
	row = [[0 for i in range(n)] for i in range(n)]
	col = [[0 for i in range(n)] for i in range(n)]
	flag = 0
	for i in range(n):
		s.append(list(input().strip()))
	for i in range(n):
		for j in range(n):
			if s[i][j] == 'X':
				s[i][j] = 1
			elif s[i][j] == '.':
				s[i][j] = 0
				flag = 1
			else:
				s[i][j] = -1
			row[i][j] = col[j][i] = s[i][j]
	for i in range(n):
		temp = []
		for j in range(n - k + 1):
			temp = s[i][j:j + k]
			if sum(temp) >= k - 1:
				return True
			temp = col[i][j:j + k]
			if sum(temp) >= k - 1:
				return True
	d1 = [0 for i in range(n)]
	d2 = [0 for i in range(n)]
	for i in range(n):
		d1[i] = s[i][i]
		d2[i] = s[i][n - i - 1]
	for i in range(n - k + 1):
		if sum(d1[i:i + k]) >= k - 1 or sum(d2[i:i + k]) >= k - 1:
			return True
	return False
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	if f(n, k):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	ans = 0
	(n, m) = [int(x) for x in input().split()]
	a = []
	nn = n
	while nn > 0:
		a.append(input())
		nn -= 1
	for i in range(n):
		for j in range(n):
			if a[i][j] == 'X':
				c = i
				d = j
				r = 0
				p = 0
				q = 0
				while c < n and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p == 0:
							p = r
						q += 1
					r += 1
					c += 1
				if r >= m:
					ans = 1
				c = i
				d = j
				r1 = 0
				p1 = 0
				q = 0
				while c >= 0 and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p1 == 0:
							p1 = r1
						q += 1
					r1 += 1
					c -= 1
				if r1 >= m:
					ans = 1
				c = i
				d = j
				r = 0
				p = 0
				q = 2
				while d < n and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p == 0:
							p = r
						q += 1
					r += 1
					d += 1
				if r >= m:
					ans = 1
				c = i
				d = j
				r1 = 0
				p1 = 0
				q = 0
				while d >= 0 and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p1 == 0:
							p1 = r1
						q += 1
					r1 += 1
					d -= 1
				if r1 >= m:
					ans = 1
				c = i
				d = j
				r = 0
				p = 0
				q = 0
				while d < n and c < n and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p == 0:
							p = r
						q += 1
					r += 1
					d += 1
					c += 1
				if r >= m:
					ans = 1
				c = i
				d = j
				r1 = 0
				p1 = 0
				q = 0
				while d >= 0 and c >= 0 and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p1 == 0:
							p1 = r1
						q += 1
					r1 += 1
					d -= 1
					c -= 1
				if r1 >= m:
					ans = 1
				c = i
				d = j
				r = 0
				p = 0
				q = 0
				while d < n and c >= 0 and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p == 0:
							p = r
						q += 1
					r += 1
					d += 1
					c -= 1
				if r >= m:
					ans = 1
				c = i
				d = j
				r1 = 0
				p1 = 0
				q = 0
				while d >= 0 and c < n and ((a[c][d] == 'X' or a[c][d] == '.') and q < 2):
					if a[c][d] != 'X':
						if p1 == 0:
							p1 = r1
						q += 1
					r1 += 1
					d -= 1
					c += 1
				if r1 >= m:
					ans = 1
	if m == 1:
		ans = 1
	if ans == 1:
		print('YES')
	else:
		print('NO')
	t -= 1


def is_row_wise(a, n, k):
	for i in range(n):
		flag = True
		cnt = 0
		for j in range(n):
			if a[i][j] == 'X':
				cnt += 1
			elif a[i][j] == '.' and flag:
				cnt += 1
				flag = False
			else:
				cnt = 0
				if a[i][j] == '.':
					cnt = 1
					if a[i][j - 1] == 'X':
						cnt = 2
				else:
					flag = True
			if cnt == k:
				return True
	return False

def is_column_wise(a, n, k):
	for i in range(n):
		flag = True
		cnt = 0
		for j in range(n):
			if a[j][i] == 'X':
				cnt += 1
			elif a[j][i] == '.' and flag:
				cnt += 1
				flag = False
			else:
				cnt = 0
				if a[j][i] == '.':
					cnt = 1
					if a[j - 1][i] == 'X':
						cnt = 2
				else:
					flag = True
			if cnt == k:
				return True
	return False

def is_diag_wise(a, n, k):
	(cnt, flag) = (0, True)
	for i in range(n):
		if a[i][i] == 'X':
			cnt += 1
		elif a[i][i] == '.' and flag:
			cnt += 1
			flag = False
		else:
			cnt = 0
			if a[i][i] == '.':
				cnt = 1
				if a[i - 1][i - 1] == 'X':
					cnt = 2
			else:
				flag = True
		if cnt == k:
			return True
	(cnt, flag) = (0, True)
	for i in range(n):
		if a[i][n - 1 - i] == 'X':
			cnt += 1
		elif a[i][n - 1 - i] == '.' and flag:
			cnt += 1
			flag = False
		else:
			cnt = 0
			if a[i][n - 1 - i] == '.':
				cnt = 1
				if a[i - 1][n - 2 - i] == 'X':
					cnt = 2
			else:
				flag = True
		if cnt == k:
			return True
	return False

def read_int():
	return int(input())

def read_int_list():
	return [int(x) for x in input().split()]

def is_chef_wins(game, n, k):
	if is_row_wise(game, n, k):
		return True
	elif is_column_wise(game, n, k):
		return True
	elif is_diag_wise(game, n, k):
		return True
	else:
		return False

def main():
	tc = read_int()
	for _ in range(tc):
		(n, k) = read_int_list()
		game = [input() for _ in range(n)]
		print('YES' if is_chef_wins(game, n, k) else 'NO')

def __starting_point():
	main()
__starting_point()


def checkRow(A, row, N, K):
	count = 0
	move = 0
	for i in range(N):
		if A[row][i] == '.':
			move = move + 1
		if not A[row][i] == 'O' and move < 2:
			count = count + 1
		elif A[row][i] == '.':
			move = 1
			count = 1
		else:
			count = 0
			move = 0
		if count == K:
			return 1
	return 0

def checkCol(A, col, N, K):
	count = 0
	move = 0
	for i in range(N):
		if A[i][col] == '.':
			move = move + 1
		if not A[i][col] == 'O' and move < 2:
			count = count + 1
		elif A[i][col] == '.':
			count = 1
			move = 1
		else:
			count = 0
			move = 0
		if count == K:
			return 1
	return 0

def checkDiag(A, row, col, N, K):
	count = 0
	move = 0
	for i in range(K):
		if A[row + i][col + i] == '.':
			move = move + 1
		if not A[row + i][col + i] == 'O' and move < 2:
			count = count + 1
		elif A[row + i][col + i] == '.':
			move = 1
			count = 1
		else:
			move = 0
			count = 0
		if count == K:
			return 1
	return 0

def chck(A, N, K):
	flag = 0
	if flag == 0:
		for i in range(N):
			flag = checkRow(A, i, N, K)
			if flag == 1:
				break
	if flag == 0:
		for j in range(N):
			flag = checkCol(A, j, N, K)
			if flag == 1:
				break
	if flag == 0:
		for i in range(N - K + 1):
			for j in range(N - K + 1):
				flag = checkDiag(A, i, j, N, K)
				if flag == 1:
					break
			if flag == 1:
				break
	return flag
for tests in range(eval(input())):
	[N, K] = list(map(int, input().split()))
	A = [''] * N
	for i in range(N):
		A[i] = input()
	if chck(A, N, K) == 1:
		print('YES')
	else:
		print('NO')


n = 0
k = 0
mat = []

def check(i, j):
	ver_count = 1
	hor_count = 1
	dial1_count = 1
	dial2_count = 1
	ti = i - 1
	tj = j
	while ti >= 0 and mat[ti][j] == 'X':
		ver_count += 1
		ti -= 1
	ti = i + 1
	while ti < n and mat[ti][j] == 'X':
		ver_count += 1
		ti += 1
	ti = i
	tj = j - 1
	while tj >= 0 and mat[i][tj] == 'X':
		hor_count += 1
		tj -= 1
	tj = j + 1
	while tj < n and mat[i][tj] == 'X':
		hor_count += 1
		tj += 1
	ti = i - 1
	tj = j - 1
	while ti >= 0 and tj >= 0 and (mat[ti][tj] == 'X'):
		dial1_count += 1
		ti -= 1
		tj -= 1
	ti = i + 1
	tj = j + 1
	while ti < n and tj < n and (mat[ti][tj] == 'X'):
		dial1_count += 1
		ti += 1
		tj += 1
	ti = i - 1
	tj = j + 1
	while ti >= 0 and tj < n and (mat[ti][tj] == 'X'):
		dial2_count += 1
		ti -= 1
		tj += 1
	ti = i + 1
	tj = j - 1
	while ti < n and tj >= 0 and (mat[ti][tj] == 'X'):
		dial2_count += 1
		ti += 1
		tj -= 1
	if ver_count >= k or hor_count >= k or dial1_count >= k or (dial2_count >= k):
		return True
	else:
		return False
t = eval(input())
while t > 0:
	(n, k) = list(map(int, input().split()))
	tn = n
	mat = []
	while tn > 0:
		mat.append(input().strip())
		tn -= 1
	canWin = False
	i = 0
	for row in mat:
		j = 0
		for cell in row:
			if cell == '.' and check(i, j):
				canWin = True
				break
			j += 1
		i += 1
	if canWin:
		print('YES')
	else:
		print('NO')
	t -= 1


def dg(m, i0, j0, d):
	return [m[(i0 + i - 1) % len(m)][(j0 + d * i - 1) % len(m[0])] for i in range(len(m))]

def column(matrix, i):
	return [row[i] for row in matrix]
import re
for _ in range(eval(input())):
	(n, k) = list(map(int, input().split()))
	f = 0
	st = 'X' * k
	a = []
	for j in range(n):
		l = input()
		a.append(list(l))
	fd = [[a[y - x][x] for x in range(n) if 0 <= y - x < n] for y in range(2 * n - 1)]
	s = list(reversed(list(zip(*a))))
	bd = [[s[y - x][x] for x in range(n) if 0 <= y - x < n] for y in range(2 * n - 1)]
	for i in range(n):
		for j in range(n):
			if a[i][j] == '.' and f == 0:
				a[i][j] = 'X'
				if len(re.findall(st, ''.join(a[i]))) != 0:
					f = 1
					print('YES')
					break
				elif len(re.findall(st, ''.join(column(a, j)))) != 0:
					f = 1
					print('YES')
					break
				a[i][j] = '.'
	if f == 0:
		for i in range(len(fd)):
			for j in range(len(fd[i])):
				if fd[i][j] == '.' and f == 0:
					fd[i][j] = 'X'
					if len(re.findall(st, ''.join(fd[i]))) != 0:
						f = 1
						print('YES')
						break
					fd[i][j] = '.'
				if bd[i][j] == '.' and f == 0:
					bd[i][j] = 'X'
					if len(re.findall(st, ''.join(bd[i]))) != 0:
						f = 1
						print('YES')
						break
					bd[i][j] = '.'
	if f == 0:
		print('NO')


def prt(temp):
	for i in temp:
		print(i)

def isin(x, a, b):
	return a <= x and x <= b

def prog():
	(n, k) = list(map(int, input().split()))
	mat = []
	dots = []
	for i in range(n):
		inp = input()
		temp = []
		for x1 in range(n):
			x = inp[x1]
			if x == 'X':
				temp += [1]
			else:
				temp += [0]
			if x == '.':
				dots += [(i, x1)]
		mat += [temp]
	if len(dots) == 0:
		return False
	mat[dots[0][0]][dots[0][1]] = 1
	if prog1(mat, n, k):
		return True
	for i in range(1, len(dots)):
		mat[dots[i - 1][0]][dots[i - 1][1]] = 0
		mat[dots[i][0]][dots[i][1]] = 1
		if prog1(mat, n, k):
			return True
	if prog1(mat, n, k):
		return True
	return False

def prog1(mat, n, k):
	temp = []
	temp1 = []
	for i in mat:
		temp += [i[:]]
		temp1 += [i[:]]
	for i in range(n):
		j = 0
		for j in range(1, k):
			temp[i][j] += temp[i][j - 1]
		if temp[i][j] == k:
			return True
		for j in range(k, n):
			temp[i][j] += temp[i][j - 1]
			if temp[i][j] - temp[i][j - k] == k:
				return True
	for i in range(n):
		for j in range(n):
			temp[i][j] = temp1[j][i]
	for i in range(n):
		j = 0
		for j in range(1, k):
			temp[i][j] += temp[i][j - 1]
		if temp[i][j] == k:
			return True
		for j in range(k, n):
			temp[i][j] += temp[i][j - 1]
			if temp[i][j] - temp[i][j - k] == k:
				return True
	for i in range(n):
		for j in range(n):
			temp[i][j] = temp1[i][j]
	for i in range(n - 1, -1, -1):
		x = i
		y = 0
		cn = 1
		while cn != k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			cn += 1
		if temp[x][y] == k:
			return True
		while cn >= k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			if temp[x][y] - temp[x - k][y - k] == k:
				return True
	for i in range(1, n):
		x = 0
		y = i
		cn = 1
		while cn != k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			cn += 1
		if temp[x][y] == k:
			return True
		while cn >= k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			if temp[x][y] - temp[x - k][y - k] == k:
				return True
	for i in range(n):
		for j in range(n):
			temp[i][j] = temp1[i][n - 1 - j]
	for i in range(n - 1, -1, -1):
		x = i
		y = 0
		cn = 1
		while cn != k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			cn += 1
		if temp[x][y] == k:
			return True
		while cn >= k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			if temp[x][y] - temp[x - k][y - k] == k:
				return True
	for i in range(1, n):
		x = 0
		y = i
		cn = 1
		while cn != k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			cn += 1
		if temp[x][y] == k:
			return True
		while cn >= k and isin(y + 1, 0, n - 1) and isin(x + 1, 0, n - 1):
			x += 1
			y += 1
			temp[x][y] += temp[x - 1][y - 1]
			if temp[x][y] - temp[x - k][y - k] == k:
				return True
	return False
t = eval(input())
for _ in range(t):
	ans = prog()
	if ans == True:
		print('YES')
	else:
		print('NO')