Lemurs

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

The jungle has a rectangular shape with dimensions $n$ by $m$. Taxicab lemurs are already known to be group animals. Furthermore, each group of lemurs inhabits only one cell of the jungle, i.e. a single cell with coordinates $(x, y)$, where $1 \leq x \leq n$ and $1 \leq y \leq m$. But the most fascinating aspect of their behaviour lies in their foraging area: if some group of lemurs inhabits a cell with coordinates $(x, y)$, then their foraging area is bounded by a ball with radius $k$ in the taxicab metric. In other words, the foraging area of this group of lemurs is the set of cells with coordinates $(x', y')$ satisfying $|x - x'| + |y - y'| \le k$ and $1 \leq x' \leq n$, $1 \leq y' \leq m$. The constant $k$ is universal for all taxicab lemurs.

The last taxicab lemur's researcher has disappeared under unknown circumstances and the only thing he left behind was an $n$ by $m$ map with some cells marked as taxicab lemurs' foraging area (the circumstances of this event are still unclear; the latest theory suggests that the newly discovered species of lemurs may not be herbivorous after all...). Slightly disturbed by that story, Bajtazar is currently wondering if this map is reliable. Therefore he would like to check if there exists such a set of groups of taxicab lemurs, that their foraging area would match precisely the cells marked on the map.

Help Bajtazar and find the answer to his bugging question. He will certainly be grateful till his very last days!

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 4\,000$). The descriptions of the test cases follow.

The first line of each test case consists of numbers $n, m, k$ ($1 \leq n, m, k \leq 1\,000$) with meaning as described in the task statement.

The next $n$ lines describe the map. If, according to the map, the taxicab lemurs forage on a cell with coordinates $(j, i)$, then in the $i$-th line on $j$-th position will be a character x, otherwise this character will be a dot.

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

For each test case print a single line. If the answer to Bajtazar's question is yes, print TAK, otherwise print NIE.

In the first test case, the marked foraging area is generated by a set of 3 groups of lemurs inhabiting cells with coordinates $(1,3)$, $(2,2)$ and $(3,1)$.

In the second test case, there does not exists such a set of groups of lemurs that would generate the foraging area described by the map.