Migrated from Lutece 149 解救小Q

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小Q被邪恶的大魔王困在了迷宫里，love8909决定去解救她。

迷宫里面有一些陷阱，一旦走到陷阱里，就会被困身亡:(，迷宫里还有一些古老的传送阵，一旦走到传送阵上，会强制被传送到传送阵的另一头。

现在请你帮助love8909算一算，他至少需要走多少步才能解救到小Q？

Input

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

每组测试数据第一行为两个整数$N$，$M$，($1\leq N, M\leq 50$)表示 迷宫的长和宽。

接下来有$N$行，每行$M$个字符，是迷宫的具体描述。

• .表示安全的位置
• #表示陷阱，
• Q表示小Q的位置
• L表示love8909所在位置，

数据保证love8909只有一个，数据也保证小Q只有一个。

小写字母a-z表示分别表示不同的传送阵，数据保证传送阵两两配对。

Output

每组数据输出一行，解救小Q所需的最少步数，如果无论如何都无法救小Q，输出-1。

Samples

2

5 5
....L
.###.
b#b#a
##.##
...Qa

5 5
....L
.###.
.#.#.
##.##
...Q.

3
-1

Resources

love8909