C. Carrying One Badge
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Elisa is late for the practice session, and the university building hosting the contest does not make it easy. The floor is a rectangle of rooms drawn as a grid of cells. Some cells are blocked by walls, some cells hold an access badge that a volunteer left on a table, and some cells hold a locked door. Every badge and every door has one of $$$K$$$ colours.

Elisa can carry at most one badge, because the readers accept a single card only. When she enters a cell that holds a badge, she may leave it there, or take it. If she takes it, the badge she was carrying before goes into the lost-and-found box and is gone for her. Badges never run out, because the volunteers keep a full box on every table: a cell that holds a badge still holds one after Elisa takes it, so she may come back to that cell later and take another badge of the same colour.

A locked door of colour $$$c$$$ can only be entered while carrying a badge of the same colour $$$c$$$. When Elisa enters it, that badge is swallowed by the reader and the door is propped open: from that moment, every door of colour $$$c$$$ on the floor is permanently unlocked and behaves like an ordinary empty cell.

Elisa never throws a badge away for nothing. She can only lose a badge by taking another one, or by using it on a locked door.

Elisa starts carrying no badge. In one step, she moves to one of the four cells that share a side with her current cell. She cannot leave the floor or enter a wall.

Entering a badge cell costs one step; choosing whether to take the badge costs no additional steps. Entering a locked door also costs one step. The required badge is spent during that step, and Elisa finishes the step inside the now unlocked door cell.

Find the minimum number of steps she needs to reach the team room.

Input

The first line contains three integers $$$H$$$, $$$W$$$, and $$$K$$$ ($$$1 \le H, W \le 50$$$, $$$H \cdot W \ge 2$$$, $$$0 \le K \le 8$$$) — the height and width of the floor, and the number of colours.

Each of the next $$$H$$$ lines contains a string of exactly $$$W$$$ characters describing one row of the floor. Each character is one of:

  • #: a wall;
  • .: an empty cell;
  • S: Elisa's starting cell;
  • T: the team room;
  • the $$$c$$$-th lowercase English letter, for $$$1 \le c \le K$$$: a badge of colour $$$c$$$;
  • the $$$c$$$-th uppercase English letter, for $$$1 \le c \le K$$$: a locked door of colour $$$c$$$.

There is exactly one S and exactly one T. A colour may have any number of badges and doors, including zero.

Output

Print one integer — the minimum number of steps needed to enter T, or -1 if it is impossible.

Examples
Input
1 2 0
ST
Output
1
Input
1 5 2
SabAT
Output
4
Input
1 6 1
SaA.AT
Output
5
Note

In the second example, Elisa takes a, but she must leave b on the table. Otherwise, she would no longer carry the badge needed to enter A.

In the third example, entering the first A spends the badge a and unlocks both doors A. The second door can then be entered without another badge.