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

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

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

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

  1、假设机器人当前处在的位置为(x,y)，朝向为d。则它的方向上的下一步的位置(x1,y1$)$ 定义如下：

     若d=0，则令(x1,y1)=(x,y+1)，

     若d=1，则令(x1,y1)=(x+1,y)，

     若d=2，则令(x1,y1)=(x,y−1)，

     若d=3，则令(x1,y1)=(x−1,y).

  2、接下来，机器人判断它下一步的位置是否在地图内，且是否为空地。具体地说，它判断(x1,y1) 是否满足1≤x1≤n,1≤y1≤m，且(x1,y1) 位置上是空地。如果条件成立，则机器人会向前走一步。它新的位置变为(x1,y1)，且朝向不变。如果条件不成立，则它会执行“向右转”操作。也就是说，令 d1$=(d+1)\mathrm{m}\mathrm{o}\mathrm{d}4$（即d+1除以4的余数），且它所处的位置保持不变，但朝向由d变为d1。

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

本题有多组测试数据。

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

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

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

第二行包含两个正整数x0,y0和一个非负整数d0。

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

说明/提示

【样例 1 解释】

该样例包含两组数据。对第一组数据，机器人的状态以如下方式变化：

1、初始时，机器人位于位置(1,1)，方向朝西(用数字2代表）。

2、第一步，机器人发现它下一步的位置(1,0)不在地图内，因此，它会执行“向右转”操作。此时，它的位置仍然为(1,1)，但方向朝北(用数字3代表)。

3、第二步，机器人发现它下一步的位置(0,1)不在地图内，因此，它仍然会执行“向右转”操作。此时，它的位置仍然为(1,1)，但方向朝东（用数字0代表）.

4、第三步，机器人发现它下一步的位置(1,2)在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为(1,2)，方向仍然朝东。

5、第四步，机器人发现它下一步的位置(1,3)在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为(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)，向右转，向右转。

【数据范围】

对于所有测试数据，保证：$1\le T\le 5,1\le n,m\le 10^3$，$1\le k\le 10^6$，1≤x0≤n，1≤y0≤m，0≤d0≤3，且机器人的起始位置为空地。

2024csp-j2