本题没有可用的提交语言。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 A 打算前往一片丛林探险。丛林地图可以用一个 $n$ 行 $m$ 列的字符表表示。第 $i$ 行第 $j$ 列的位置坐标为 $(i,j)$。若该位置字符为 x，表示有障碍、不可通过；若字符为 .，表示空地、可以通过。

机器人的状态由位置和朝向组成。位置 $(x,y)$ 表示机器人位于第 $x$ 行第 $y$ 列；朝向用 $0$ 到 $3$ 的整数 $d$ 表示，其中 $d=0$ 向东、$d=1$ 向南、$d=2$ 向西、$d=3$ 向北。初始位置为 $(x_0,y_0)$，朝向为 $d_0$，且初始位置保证是空地。

机器人将执行 $k$ 次操作。每次操作时，先根据当前朝向确定下一格：朝东为 $(x,y+1)$，朝南为 $(x+1,y)$，朝西为 $(x,y-1)$，朝北为 $(x-1,y)$。若下一格在地图内且是空地，机器人就向前走一步，朝向不变；否则机器人原地向右转，朝向变为 $(d+1)\bmod 4$。

求机器人执行完 $k$ 次操作后，地图上被它经过的位置（包括起始位置）共有多少个。

输入格式

从文件 explore.in 中读入数据。本题有多组测试数据。

第一行包含一个正整数 $T$，表示数据组数。接下来每组数据的格式如下：

• 第一行包含三个正整数 $n,m,k$，分别表示地图行数、列数和机器人操作次数。
• 第二行包含两个正整数 $x_0,y_0$ 和一个非负整数 $d_0$，分别表示机器人的初始位置和朝向。
• 接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，只包含 x 和 .。第 $x$ 行字符串的第 $y$ 个字符表示位置 $(x,y)$ 的状态。

保证机器人初始所在的位置为空地。

输出格式

输出到文件 explore.out 中。

对于每组数据，输出一行一个正整数，表示机器人经过的位置数量。

样例

2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....

3
13

样例解释：该样例包含两组数据。

对于第一组：初始位置为 $(1,1)$，朝向为西（方向 $2$）。第 1 步，下一格 $(1,0)$ 不在地图内，机器人原地右转，朝北（方向 $3$）；第 2 步，下一格 $(0,1)$ 不在地图内，再次右转，朝东（方向 $0$）；第 3 步向东走到 $(1,2)$；第 4 步向东走到 $(1,3)$。因此经过的位置为 $(1,1),(1,2),(1,3)$。

对于第二组，机器人依次向东走到 $(1,2),(1,3),(1,4),(1,5)$，右转后向南走到 $(2,5),(3,5),(4,5),(5,5)$，右转后向西走到 $(5,4),(5,3),(5,2)$，右转后向北走到 $(4,2)$，随后连续右转两次，向南走到 $(5,2)$，再连续右转两次。经过的位置总数为 $13$。

数据范围与特殊性质

所有测试数据满足：$1\le T\le5$，$1\le n,m\le10^3$，$1\le k\le10^6$，$1\le x_0\le n$，$1\le y_0\le m$，$0\le d_0\le3$。

“全局范围”表示仅使用本节开头给出的该项全局数据范围。