Lemurs

Bajtazar has been sent on a mission to the jungle. He is going to study the behavior of a newly discovered species, taxicab lemurs.

Taxicab lemurs are known to live in groups. Each group lives in exactly one cell $(x, y)$ of the jungle, where $1 \leq x \leq n$ and $1 \leq y \leq m$. The jungle is an $n \times m$ rectangle. The foraging area of a group is the ball of taxicab radius $k$ around its cell: the set of cells $(x', y')$ with $|x - x'| + |y - y'| \leq k$, $1 \leq x' \leq n$, and $1 \leq y' \leq m$. The constant $k$ is the same for all groups.

The last researcher on this expedition has disappeared, leaving behind an $n \times m$ map where some cells are marked as foraging area. The circumstances are unclear. The latest theory suggests the newly discovered species may not be herbivorous after all.

Bajtazar wants to know whether the map can be trusted. He asks whether there is a set of groups whose foraging areas match exactly the marked cells.

The first line contains the number of test cases $z$ ($1 \leq z \leq 4\,000$). Each test case follows.

The first line of each test case contains $n$, $m$, and $k$ ($1 \leq n, m, k \leq 1\,000$), with the meanings given in the statement.

The next $n$ lines describe the map. If the map shows lemurs foraging on cell $(j, i)$, then the $j$-th character of the $i$-th line is x. Otherwise it is a dot.

The sum of $n + m + k$ over all test cases does not exceed $100\,000$.

For each test case, print one line. Print TAK if such a set of groups exists, otherwise print NIE.

In the first test case, the marked foraging area is produced by three groups living in cells $(1, 3)$, $(2, 2)$, and $(3, 1)$.

In the second test case, no set of groups produces the foraging area shown on the map.