在一张 $n\times m$ 的地图上，字符 $\texttt{.}$ 表示可通行的空地，$\texttt{x}$ 表示障碍物。机器人初始位于 $(x_0,y_0)$；方向 $0,1,2,3$ 分别表示东、南、西、北。

机器人执行恰好 $k$ 次操作。每次操作中，若正前方一格仍在地图内且为可通行空地，则机器人前进一格；否则机器人原地顺时针右转 $90^\circ$。转向本身也计作一次操作。

求机器人曾到达过的不同格子数，起点也应计入。

输入格式

第一行一个整数 $T$，表示测试数据组数。

每组数据的第一行包含三个整数 $n,m,k$；第二行包含三个整数 $x_0,y_0,d_0$；随后给出 $n$ 行地图。

坐标从 $1$ 开始编号，且起点保证是空地。

输出格式

对每组数据输出一行一个整数，表示经过的不同格子数量。

样例 1

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

3
13

数据范围与原题特殊限制

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

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。