题目描述

我的名字是工藤新一 是解决困难案件的高中生名侦探 可是有一天被神秘的组织灌下了毒药 身体缩小了 变成了江户川柯南 身体虽然变小 头脑还是一样 不管什么案件 真相永远只有一个 ——江户川柯南

为了躲避黑暗组织的追踪，柯南不慎逃入一个远古的迷宫，机智的柯南马上通过卫星电话手表从阿笠博士那获取了迷宫地图。不幸的是，迷宫的出口有3个钥匙插槽，必须同时集齐这3把不同的钥匙才能打开出口的门。而这3把钥匙分别分布在迷宫中不同的地方。 假设只有移动需要时间，柯南只能上下左右移动，并且每秒只能移动一格，迷宫中的墙壁无法穿越。柯南再不逃离，黑暗组织就要追进来了。他能逃离吗？如果能，最快需要多少秒才能打开出口逃离迷宫呢？

输入输出格式

输入

输入数据的第一行是一个整数T，表示有T组测试样例，接着是T块数据，每块数据先是两个整数n和m，分别表示迷宫的行数和列数，接着是个n行m列的字符矩阵表示迷宫地图，一个字符代表迷宫一格，’S’表示柯南当前所在地，’D’表示出口，’.’表示普通的路，’*’表示墙壁，’A’、’B’、’C’分别表示3把不同的钥匙。T<=10，2<n,m<=20。

输出

对于每组测试样例，如果柯南可以逃离，输出柯南逃离迷宫所需最短时间并独占一行；如果柯南无法逃离，输出-1并独占一行。

样例

输入1

2
3 3
D.C
*..
SAB
4 3
D*A
..*
S.B
.C.

输出1

6
-1

时间及空间限制

1s, 256MB.