Bajtazar 被派往丛林执行任务。他将研究一种新发现的物种——出租车狐猴（taxicab lemurs）的行为。

丛林是一个尺寸为 $n \times m$ 的矩形区域。已知出租车狐猴是群居动物。此外，每一群狐猴只居住在丛林中的一个单元格内，即坐标为 $(x, y)$ 的单个单元格，其中 $1 \le x \le n$ 且 $1 \le y \le m$。但它们行为中最迷人的一点在于它们的觅食区域：如果某一群狐猴居住在坐标为 $(x, y)$ 的单元格中，那么它们的觅食区域由出租车度量下半径为 $k$ 的球体所界定。换句话说，这群狐猴的觅食区域是满足 $|x - x'| + |y - y'| \le k$ 且 $1 \le x' \le n, 1 \le y' \le m$ 的所有坐标为 $(x', y')$ 的单元格集合。常数 $k$ 对所有出租车狐猴都是通用的。

上一位研究出租车狐猴的研究员在不明情况下失踪了，他留下的唯一东西是一张 $n \times m$ 的地图，上面标记了一些单元格作为出租车狐猴的觅食区域$^1$。对此感到不安的 Bajtazar 目前正在怀疑这张地图是否可靠。因此，他想检查是否存在这样一组出租车狐猴群体，使得它们的觅食区域恰好与地图上标记的单元格相吻合。

请帮助 Bajtazar 找到这个困扰他的问题的答案。他一定会感激你直到他生命的最后一天！

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 4000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含数字 $n, m, k$ ($1 \le n, m, k \le 1000$)，含义如题目描述所述。

接下来的 $n$ 行描述了地图。如果根据地图，出租车狐猴在坐标为 $(j, i)$ 的单元格觅食，则第 $i$ 行的第 $j$ 个位置将是一个字符 x，否则该字符为一个点 .。

所有测试用例的 $n + m + k$ 之和不超过 $100\,000$。

输出格式

对于每个测试用例，打印一行。如果 Bajtazar 问题的答案是肯定的，打印 TAK，否则打印 NIE。

$^1$ 事件的情况尚不清楚。最新的理论表明，这种新发现的狐猴物种可能根本不是食草动物……

样例

输入 1

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

输出 1

TAK
NIE

说明

在第一个测试用例中，标记的觅食区域由居住在坐标 $(1, 3), (2, 2)$ 和 $(3, 1)$ 的 3 群狐猴产生。

在第二个测试用例中，不存在这样一组狐猴群体能产生地图所描述的觅食区域。