2011年3月16日以来，利比亚爆发的骚乱不断升级，已严重危及到普通民众和各国在利比亚工作的人员的安全。为了尽快救出在利比亚的同胞，根据利比亚的形势，我国政府告诉每个在利比亚的公民，如何行动才能最快地到达安全的地方，然后由我国派出的飞机、轮船、汽车接回国。

假设利比亚的地图可以描述为一个n行m列的长方形，待拯救的同胞小A在1行1列处，安全的目标位置在n行m列处。小A每次只能向相邻的上、下、左、右四个方向移动，即如果小A现在的位置是i行j列，小A的下一步位置将到达i-1行j列、i+1行j列、i行j-1列、i行j+1列这四个位置之一，当然小A不能移出n行m列的长方形。

利比亚是一个多沙漠且地形复杂的国家，某些位置是很危险的，人不能去。

给出利比亚的地图,请告诉小A从起点(1,1)走到终点(n,m)最快需要多少步呢？。

第一行有2个正整数n,m (1≤n≤2000，1≤m≤2000)，它们之间以一个空格分隔，表示利比亚的地形可以分为n行m列。

接下来n行,每行m个字符,分别表示地图中该位置的信息。其中：

字符“*”表示这个位置是建筑物、河流、有地雷等人无法走到的位置（保证起点终点不是“*”）;

小数点“.”表示人可以走到该位置。

只有一行，该行只有一个正整数。表示为小A从起点到终点，最快需要多少步。

【样例说明】

小A最快走法是：

1行1列→2行1列→2行2列→2行3列→1行3列→1行4列→1行5列→2行5列→3行5列

【数据说明】

60%的数据中，1≤n≤100，1≤m≤100；

80%的数据中，1≤n≤250，1≤m≤250；

90%的数据中，1≤n≤500，1≤m≤500；

100%的数据中，1≤n≤2000，1≤m≤2000。