题目描述

遗迹深处有一层 $n$ 行 $m$ 列的石室，格子的含义是：

• . 普通地面，可以踩；
• # 塌方区，不能通行；
• S 入口，T 宝库（都算可以通行，且都不是传送门）；
• 1 $\sim$ 4 是成对的传送门，同一个数字恰好出现两次。

探险者每走一步（上下左右相邻格）花 $1$ 个时间单位。如果走进了一个传送门格子，会立刻被传送到同一数字的另一格，传送本身不额外花时间（也就是这一步的总花费还是 $1$）；传送落点不会再次触发传送。

请算一算从 S 到 T 最少要花多少时间。走不到就输出 $-1$。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串。

输出格式

一行一个整数，表示最少时间；无法到达输出 $-1$。

输入输出样例 #1

输入 #1

3 5
S.1..
.#1..
....T

输出 #1

5

说明

数据范围

• 对于 $100\%$ 的数据，$2\le n,m\le 200$，传送门不超过 $4$ 对。