F. 伊戈尔与山
每个测试点时间限制：5 秒
内存限制：512 兆字节

IT 校园 "NEIMARK" 的参观者不仅是强大的程序员，也是体格健壮的人！有人练习游泳，有人练习划船，还有人练习攀岩！

伊戈尔大师是当地攀岩社区的杰出人物。一天，他去登山，准备攀登其中一座山峰。作为一名经验丰富的攀登者，伊戈尔决定不走现有的路径，而是利用自己的技能严格垂直向上攀爬。

伊戈尔找到了山的一个矩形垂直截面，并把它在心理上划分为 $n$ 个水平层。然后他用垂直隔板将每一层划分为 $m$ 个段。在检查这些段时，伊戈尔发现了一些可以抓握的方便突起（以下称为支点）。因此，所选的山体部分可以表示为一个 $n \times m$ 的矩形，其中某些格子含有支点。

作为一名经验丰富的程序员，伊戈尔决定计算有效路径的数量。一条路径被定义为一个互不相同的支点的序列。一条路径被认为是有效的，如果满足以下条件：

• 路径中的第一个支点位于最底层（第 $n$ 行）；
• 路径中的最后一个支点位于最顶层（第 $1$ 行）；
• 每个后续支点不低于前一个支点（即行号只能减小或不变）；
• 每一层至少使用一个支点（即矩形的每一行都至少有一个支点被选中）；
• 每一层最多使用两个支点（因为伊戈尔只有两只手）；
• 伊戈尔可以从当前支点移动到下一个支点，如果两个对应段中心的欧几里得距离不超过伊戈尔的臂展 $d$。

段 $(i_1, j_1)$ 与 $(i_2, j_2)$ 之间的距离为：

计算不同有效路径的数量。如果两条路径使用的支点列表不同，或支点被访问的顺序不同，则视为不同。

输入格式

每个测试文件包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含三个整数 $n$、$m$、$d$（$2 \le n \le 2000$，$1 \le m, d \le 2000$）。

接下来 $n$ 行，每行包含 $m$ 个字符 —— 山体对应层的描述。字符 '#' 表示空段，字符 'X' 表示有支点的段。这些层从上到下给出。

保证所有测试用例的 $n \cdot m$ 之和不超过 $4 \cdot 10^6$。

输出格式

对于每个测试用例，输出有效路径的数量，对 $998244353$ 取模。

示例输入

3
3 4 1
XX#X
#XX#
#X#X
3 4 2
XX#X
#XX#
#X#X
3 1 3
X
X
#

示例输出

2
60
0

提示

• 第一个案例中的可能路线：
  （图示）

• 第二个案例中，伊戈尔的臂展变大了，因此出现了新的路线，例如：
  （图示）

  

• 第三个案例中，最底层没有支点，因此没有有效路线。