Background

Special for beginners, ^_^

Description

给定一个二维地图，有 N 行 M 列，小 A 在左上角的（1，1）处，小 A 的老板在（N,M）处，地图中有三种标，标 0 的，表示有路可以走，标 1 的表示是桩，必须绕开，标大写字母，则直接可以传送到另外一个的该大写字母处，且不需要步数。地图中保证同样的大写字母仅有两个。

求小 A 最少需要多少步数可以到达 BOSS 处。

Format

Input

第一行 2 个数据：n m；

下面 n 行，每行 m 个数，表示地图。地图数据之间无空格。每步只能走一格，方向上下左右。左上角为入口点,右下角为出口点.

Output

一个整数，表示小 A 最少需要走多少步。如果小 A 不能走到目标，则输出 No Solution.

Samples

3 4
0000
00A0
A000

4

Limitation

对 60%的数据,n,m<=20

对 100%的数据,n,m<=100

数据保证 入口和BOSS点 非0，1和大写字母。 地图中保证字母成队出现。传送时可以传回来（不费时间），相当于到该字母处不传送 无路时输出：No Solution. 后面有这个点