Background

世事洞明皆学问，人情练达即文章。

Description

小 Q 被邪恶的大魔王困在了迷宫里, love8909 决定去解救她. 迷宫里面有一些陷阱, 一 E走到陷阱里, 就会被困身亡:(, 迷宫里还有一些古老的传送阵, 一E走到传送阵上, 会强制被 传送到传送阵的另一头.
现在请你帮助 love8909 算一算, 他至少需要走多少步才能解救到小 Q?

Format

Input

第一行为一个整数 T, 表示测试数据组数.
每组测试数据第一行为两个整数 N, M, (1 ≤ N, M ≤ 50) 表示迷宫的长和宽. 接下来有 N 行, 每行 M 个字符, 是迷宫的具体描述.

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

数据保证 love8909 只有一个, 数据也保证小 Q 只有一个.
小写字母 a-z 表示分别表示不同的传送阵, 数据保证传送阵两两配对.

Output

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

Sample

Input

2
5 5
....L
.###.
b#b#a
##.##
...Qa 5 5
....L
.###.
.#.#.
##.##
...Q.

Output

3
-1

Limitation

对于 30% 的数据, 有传送阵的数目为 0. T ≤ 10
对于 100% 的数据, 满足传送阵的数目 ≤ 26. T ≤ 10
1s, 128000KiB for each test case.

Hint

Source

CDQZ TEST