1630: [CSP-J 2024] 地图探险

小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂，为了防止迷路，他先派遣了一个机器人前去探路。

丛林的地图可以用一个 $n$ 行 $m$ 列的字符表来表示。我们将第 $i$ 行第 $j$ 列的位置的坐标记作 $(i,j)(1\le i\le n,1\le j\le m)$。如果这个位置的字符为 $\mathtt{x}$，即代表这个位置上有障碍，不可通过。反之，若这个位置的字符为 $\mathtt{.}$，即代表这个位置是一片空地，可以通过。

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 $(x,y)(1\le x\le n,1\le y\le m)$ 刻画，它表示机器人处在地图上第 $x$ 行第 $y$ 列的位置。而朝向用一个 $0\sim 3$ 的 整数 $d$ 表示，其中 $d=0$ 代表向东，$d=1$ 代表向南，$d=2$ 代表向西，$d=3$ 代表向北。

初始时，机器人的位置为 $(x_0,y_0)$，朝向为 $d_0$。保证初始时机器人所在的位置为空地。接下来机器人将要进行 $k$ 次操作。每一步，机器人将按照如下的模式操作：

1. 假设机器人当前处在的位置为 $(x,y)$，朝向为 $d$。则它的方向上的下一步的位置 $(x^{\text{′}},y^{\text{′}})$ 定义如下：若 $d=0$，则令 $(x^{\text{′}},y^{\text{′}})=(x,y+1)$，若 $d=1$，则令 $(x^{\text{′}},y^{\text{′}})=(x+1,y)$，若 $d=2$，则令 $(x^{\text{′}},y^{\text{′}})=(x,y-1)$，若 $d=3$，则令 $(x^{\text{′}},y^{\text{′}})=(x-1,y)$。

2. 接下来，机器人判断它下一步的位置是否在地图内，且是否为空地。具体地说，它判断 $(x^{\text{′}},y^{\text{′}})$ 是否满足 $1\le x^{\text{′}}\le n,1\le y^{\text{′}}\le m$，且 $(x^{\text{′}},y^{\text{′}})$ 位置上是空地。如果条件成立，则机器人会向前走一步。它新的位置变为 $(x^{\text{′}},y^{\text{′}})$，且朝向不变。如果条件不成立，则它会执行“向右转”操作。也就是说，令 $d^{\text{′}}=(d+1)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>4$（即 $d+1$ 除以 $4$ 的余数），且它所处的位置保持不变，但朝向由 $d$ 变为 $d^{\text{′}}$。

小 A 想要知道，在机器人执行完 $k$ 步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个正整数 $n,m,k$。其中 $n,m$ 表示地图的行数和列数，$k$ 表示机器人执行操作的次数。

第二行包含两个正整数 $x_0,y_0$ 和一个非负整数 $d_0$。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。保证字符串中只包含 $\mathtt{x}$ 和 $\mathtt{.}$ 两个字符。其中，第 $x$ 行的字符串的第 $y$ 个字符代表的位置为 $(x,y)$。这个位置是 $\mathtt{x}$ 即代表它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。

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

3
13