K. Treasures
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aylin is in a maze with several treasures and wants to know the maximum number of treasures she can gather. Each square of the maze can contain treasures (whose quantity per square is represented by a digit between 1 and 9), a trap 'T', an empty space '.', or a wall '#'.

An interesting detail is that the maze is in complete darkness and she must blindly traverse the entire maze, with movements allowed up, down, left, or right. She can know if there are traps around her position (cell above, below, left, or right), but she does not know in which direction the trap is. She will not take risks, so she will avoid moving forward in her journey if there are traps around her, being able to safely retreat to a position without danger even if it has already been traversed.

Input

The input consists of multiple test cases.

Each case begins with a line with 2 integers $$$N, M$$$ $$$(1 \leq N,M \leq 10^3)$$$ followed by N lines with M characters each, which is the map description. There is a square that contains the letter 'S' representing Aylin's initial position. It is guaranteed that there is only one 'S' square for each test case.

Output

For each case, print a line with an integer indicating the maximum number of treasures that Aylin can gather.

Example
Input
4 9
S......T.
#####.###
111.#.111
..T....T.
4 7
S....T1
..111..
..1T1..
..111..
2 5
.23..
.3T.S
Output
2
5
3