题目描述

有一个 $n\times m$ 的矩形网格。每一群狐猴住在某个格子 $(x,y)$，其觅食范围是曼哈顿距离不超过 $k$ 的所有格子，即满足

的格子集合。

现在给出一张地图，其中 x 表示被标为觅食区域的格子，. 表示不是觅食区域。问是否存在若干个狐猴居住点，使它们觅食范围的并集恰好等于地图中所有 x 格子。

输入格式

第一行整数 $z$。每组数据第一行三个整数 $n,m,k$。接下来 $n$ 行，每行一个长度为 $m$ 的字符串。

输出格式

若存在合法居住点集合，输出 TAK；否则输出 NIE。

数据范围

$1\le n,m,k\le1000$，所有测试的 $n+m+k$ 之和不超过 $100000$。

样例

输入：

2
3 3 1
.xx
xxx
xx.
3 4 1
..xx
x.xx
x..x

输出：

TAK
NIE