CF2091F.Igor and Mountain

IT Campus "NEIMARK" 的访客不仅是优秀的程序员，更是体魄强健的运动爱好者！有人练习游泳，有人划船，还有人进行攀岩！

Igor 大师是当地攀岩界的知名人物。某天，他前往山区攀登一座山峰。作为经验丰富的攀岩者，Igor 决定不沿既有路线，而是利用自己的技巧严格垂直攀登。

Igor 找到了一块垂直的矩形山体区域，并将其在脑海中划分为 $n$ 个水平层。随后他将每层用垂直隔板分割为 $m$ 个区段。观察这些区段时，Igor 发现了可供抓握的凸起（以下称为支点）。因此，所选山体区域可表示为 $n \times m$ 的矩形，其中某些单元格包含支点。

作为资深程序员，Igor 决定计算有效路线的数量。路线被定义为由不同支点组成的序列。当满足以下条件时，路线被视为有效：

• 路线中第一个支点位于最底层（第 $n$ 行）；
• 路线中最后一个支点位于最顶层（第 $1$ 行）；
• 每个后续支点不低于前一个支点；
• 每层（即矩形的每一行）至少使用一个支点；
• 每层最多使用两个支点（因 Igor 只有双手）；
• 当相邻支点对应区段中心点的欧氏距离不超过 Igor 的臂展时，才能从当前支点移动到下一个支点。

Igor 的臂展为 $d$，这意味着当两个支点对应区段中心点的欧氏距离不超过 $d$ 时可进行移动。区段 $(i_1, j_1)$ 与 $(i_2, j_2)$ 之间的距离计算公式为 $\sqrt{(i_1 - i_2)^2 + (j_1 - j_2)^2}$。

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

每个测试包含多个测试用例。第一行包含测试用例数量 $t$ ($1 \leq t \leq 10^3$)。接下来是测试用例描述。

每个测试用例的第一行包含三个整数 $n$、$m$、$d$ ($2 \leq n \leq 2000$, $1 \leq m, d \leq 2000$)。

接下来的 $n$ 行每行包含 $m$ 个字符 —— 描述山体各层情况。字符 '#' 表示空区段，'X' 表示含支点的区段。层数描述顺序为从上到下。

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

对于每个测试用例，输出不同路线数量对 $998244353$ 取模后的结果。

第一个样例中的可能路线：

第二个样例中 Igor 的臂展增大，因此新路线可用，例如：

第三个样例中底层没有支点，因此不存在有效路线。

翻译由 DeepSeek R1 完成