Fish 非常擅长玩迷宫游戏，并成为了迷宫之王。这一次，他转而设计了一个棘手的迷宫游戏，并邀请 Ruins 来解谜。

迷宫可以简单地看作一个 $N \times M$ 的网格，其中一些单元格是墙壁，无法进入。在这个游戏中，Ruins 从一个单元格出发，如果相邻的单元格为空，他可以移动到任何四个连通的邻居单元格中。迷宫中路径的长度定义为他从起点到终点所必须走的步数，他的目标是逃离迷宫。由于他很聪明，他总是采用最短路径策略：他总是选择从当前单元格到出口的最短路径，并移动到该路径上的下一个单元格。如果有多个可用的单元格，他会按照上方 $(x - 1, y)$、下方 $(x + 1, y)$、左侧 $(x, y - 1)$、右侧 $(x, y + 1)$ 的顺序考虑，并移动到（在某条最短路径上的）可用单元格（如果他当前位于 $(x, y)$）。

Fish 的迷宫有一点不同：除了所有迷宫游戏中都有的出口、墙壁和空地外，还有一种特殊的单元格：升降梯（lift）。它是可控的，因此 Fish 可以随时将这种单元格变为墙壁或空地。为了让游戏更有趣，在 Ruins 下一步移动之前，Fish 会将一些升降梯单元格（或不改变）变为墙壁，让其余的变为空地，然后等待 Ruins 的决定。当然，如果 Ruins 正站在一个升降梯单元格上，Fish 就不能将该单元格变为墙壁。

请帮助 Fish 找到一种策略，尽可能长时间地将 Ruins 困在迷宫中！

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例： 第一行包含三个整数 $N, M, Q$，分别表示迷宫的行数、列数以及你需要处理的起点数量。

接下来 $N$ 行，第 $i$ 行包含一个长度为 $M$ 的字符串，表示迷宫的一行，其中第 $j$ 个字符表示单元格 $(i, j)$。在迷宫中，“.” 表示空地，“#” 表示墙壁，“?” 表示升降梯单元格，“E” 表示出口。保证迷宫中恰好有一个 “E”。

接下来 $Q$ 行，每行包含两个整数 $x, y$，表示 Ruins 在给定迷宫中的起点，起点永远不会是墙壁。

输出格式

对于每个测试用例，首先输出 Case x:，其中 $x$ 表示从 1 开始的用例编号。 然后输出 $Q$ 行，每行包含一个整数，表示对于给定的起点，你能将 Ruins 困在迷宫中的最长时间。如果你能永远困住他，输出 -1。

样例

样例输入 1

2
4 5 4
..E..
.....
.?#?.
.....
1 1
4 1
4 2
4 3
4 7 6
...E...
.......
.??#??.
.......
1 1
4 1
4 2
4 3
4 4
4 5

样例输出 1

Case 1:
2
5
6
-1
Case 2:
3
6
-1
-1
-1
-1

数据范围

$1 \le T \le 100$ $1 \le N, M \le 50$ 记迷宫中 “?” 的数量为 $K$，$0 \le K \le 10$ $1 \le Q \le N \times M$ $1 \le x \le N$ $1 \le y \le M$ 对于 90% 的测试用例：$\max(N, M) \le 10$