레무르

밥타자르는 정글로 임무를 떠났다. 그는 새로 발견된 종인 택시캡 레무르의 행동을 연구하려 한다.

택시캡 레무르는 무리를 지어 산다. 각 무리는 정글의 칸 $(x, y)$ 하나에만 산다. 여기서 $1 \leq x \leq n$, $1 \leq y \leq m$이다. 정글은 $n \times m$ 크기의 직사각형이다. 무리의 먹이 활동 영역은 그 칸을 중심으로 택시캡 거리 $k$ 안에 드는 칸이다. 즉 $|x - x'| + |y - y'| \leq k$, $1 \leq x' \leq n$, $1 \leq y' \leq m$을 만족하는 칸 $(x', y')$의 집합이다. 상수 $k$는 모든 무리에 같다.

이 탐사를 맡았던 마지막 연구자가 실종되었다. 그가 남긴 것은 일부 칸이 먹이 활동 영역으로 표시된 $n \times m$ 지도 하나뿐이다. 사건의 경위는 분명하지 않다. 최근 가설에 따르면 이 새로운 종은 초식성이 아닐 수도 있다.

밥타자르는 이 지도를 믿어도 되는지 알고 싶다. 먹이 활동 영역이 표시된 칸과 정확히 일치하는 무리의 집합이 존재하는지 묻고 있다.

첫 줄에 테스트 케이스의 개수 $z$ ($1 \leq z \leq 4\,000$)가 주어진다. 각 테스트 케이스가 그 뒤를 잇는다.

각 테스트 케이스의 첫 줄에는 $n$, $m$, $k$ ($1 \leq n, m, k \leq 1\,000$)가 주어진다. 이 값들의 의미는 문제 설명과 같다.

다음 $n$개의 줄은 지도를 나타낸다. 지도에서 레무르가 칸 $(j, i)$에 먹이 활동 영역을 두고 있다면, $i$번째 줄의 $j$번째 문자는 x이다. 그렇지 않으면 점(.)이다.

모든 테스트 케이스에 걸친 $n + m + k$의 합은 $100\,000$을 넘지 않는다.

각 테스트 케이스마다 한 줄을 출력한다. 조건을 만족하는 무리의 집합이 있으면 TAK, 없으면 NIE를 출력한다.

첫 번째 테스트 케이스에서 표시된 먹이 활동 영역은 $(1, 3)$, $(2, 2)$, $(3, 1)$ 칸에 사는 세 무리가 만든 것이다.

두 번째 테스트 케이스에서는 지도가 보여 주는 먹이 활동 영역을 만들어 내는 무리의 집합이 존재하지 않는다.