Don't Block My Car

During the National Day holiday, the streets are crowded with traffic, and parking lots are overflowing, making it easy to drive in but difficult to drive out. On the most congested day of the holiday, Old Zhang drove to the Northeast and parked his car in the Northeast Rainforest Parking Lot.

The Rainforest Parking Lot can be viewed as an $N \times M$ matrix. Each car occupies a rectangular space with a width of 1 grid and a length of at least 2 grids, as shown in the figure below:

Old Zhang's BMW (the gray car in the third row of the figure) now wants to drive out of the parking lot, but he is blocked inside. To get out, he must rely on his own physical strength and your intelligence.

Since Old Zhang does not have superhuman strength, even if he tries his best, he can only push his car forward or backward. For example, the vehicles in the figure can only move along the indicated directions, or move backward after moving forward (that is, they can only wander between these positions):

Assume that the physical strength required for Old Zhang to push a car by one grid is 1 point (his own car does not need to be pushed, of course; it can be driven directly, but it can also only move forward and backward). So, what is the minimum physical strength required for Old Zhang to drive his car out of the parking lot?

Input

The first line contains $N$ and $M$, representing the size of the parking lot.

The next $N$ lines each contain $M$ characters, representing the situation at each position in the parking lot.

'#' represents the boundary of the parking lot, '*' represents an empty space, Old Zhang's car is represented by the character '0', and every other car is represented by a lowercase letter. It is guaranteed that different cars have different characters.

The exit of the parking lot is represented by the character 'E'. It is guaranteed that there is only one exit, and it is always in the same row or column as Old Zhang's car.

Output

A single integer representing the minimum physical strength consumed for Old Zhang's car to drive out.

Examples

Input 1

6 7
#######
#*cc**#
#*bbd*#
#00adeE
#**a*e#
#######

Output 1

7

Constraints