U524402 简易迷宫

笙霄建立了一个简单的迷宫小游戏，迷宫大小为$N×M$，由若干个格子组成，玩家可以消耗$1$个单位的时间从一个格子移动到上下左右相邻的一个格子中，有些格子中可能由障碍物，玩家不能移动到有障碍物的格子中，障碍物用`#`表示，玩家起点用`S`表示，迷宫的出口用`E`表示，其它可以到达的格子用`.`表示。**玩家不能到达迷宫区域外**。 为了增加迷宫的趣味性，笙霄还在迷宫中增加了$K$个机关，机关本体在迷宫的第$x1$行$y1$列，玩家到达机关所在格子后（机关所在格子是可以到达的），可以摧毁迷宫中第$x2$行$y2$列的障碍物，**操作机关的时间可以忽略不记，一个格子中可能有多个机关**。 笙霄生成了很多关卡，他想知道，对每个迷宫，从起点到出口最少需要多少时间。

**每个测试点有多组测试数据**。 第一行有一个正整数$T$，表示测试数据的数量。 接下来对于每个测试数据： 第一行$3$个整数$N，M，K(N，M≤100，K≤10)$，表示迷宫的行数、列数、机关的数量。 接下来$N$行，每行$M$个整数，第$i$行$j$列代表迷宫第$i$行$j$列处是起点、障碍物、可通行的格子或迷宫的出口。 接下来$K$行，每行$4$个整数$x1，y1，x2，y2(1≤x1,x2≤N，1≤y1,y2≤M)$，表示机关在$x1$行$y1$列的格子中，机关可以摧毁$x2$行$y2$列的障碍物。 题目保证所有测试数据，$\sum_{i=1}^TN·M≤10^4$

一行一个整数$R$，表示最短的移动时间，题目保证一定存在一条路径和相关操作，可以从起点到达迷宫的出口。

对第一组样例，需要先去$(3, 2)$操作机关，然后前往终点 对第二组样例，可以先去$(3，1)$操作机关，然后前往$(5，5)$操作机关，是最短路径。