В цифровом лабиринте размером n на m каждая ячейка может быть:

• # — повреждённый сектор, пройти нельзя;
• . — обычный открытый сектор;
• S — точка входа в лабиринт;
• T — целевой узел;
• a...f — цифровые ключи доступа;
• A...F — защищённые двери.

За один ход можно перейти в соседнюю по стороне ячейку, если она не является повреждённым сектором.

Чтобы пройти через дверь A, нужно уже иметь ключ a, через дверь B — ключ b, и так далее.

Если агент попадает в ячейку с ключом, этот ключ немедленно добавляется в набор доступов и остаётся у агента до конца маршрута.

Требуется определить минимальное количество ходов, необходимое, чтобы добраться из S в T.

Если это невозможно, выведите -1.

Входные данные

В первой строке даны два целых числа n и m.

В следующих n строках записано по строке длины m, описывающей цифровой лабиринт.

Гарантируется, что в лабиринте ровно одна ячейка S и ровно одна ячейка T. Каждый ключ и каждая дверь могут встречаться несколько раз, при этом используются только символы от a до f и от A до F.

Выходные данные

Выведите одно целое число — минимальное количество ходов от S до T, либо -1, если добраться невозможно.

Ограничения

• 1 <= n, m <= 200
• n * m <= 40000
• Количество различных типов ключей не больше 6

Примеры

Пример 1

Входные данные

1 2
ST

Выходные данные

1

Пример 2

Входные данные

1 4
SaAT

Выходные данные

3