穿过巨大的停车场不仅耗时，而且由于车辆阻挡了去路，你甚至可能会迷路！

想象一下，你正在穿过一个有 $r$ 行 $c$ 列停车位的停车场。所有的停车位都是单位正方形。每个停车位要么是空的，要么停着一辆车。你可以在空停车位中向任意方向行走，但如果停车位里有车，你只能沿着该停车位的边界行走。你从停车场的左上角出发，以每秒一个单位距离的恒定速度行走。如果你选择最快的路线，你需要多少秒才能走到停车场的右下角？

图片展示了第一个样例中停车场的两条可能路线。蓝色路线是该情况下的最快路线。红色路线展示了你可以沿着停放车辆的边界行走。

输入格式

第一行包含两个整数 $r$ 和 $c$ ($1 \le r, c \le 50$)。 接下来的 $r$ 行，每行包含一个长度为 $c$ 的字符串，表示从上到下的每一行停车位。点号 . 表示空停车位，井号 # 表示停有车辆的停车位。

输出格式

输出你走到停车场右下角所需的最短时间（以秒为单位）。如果你的答案与正确答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例

样例输入 1

4 4
..#.
.#.#
###.
.#..

样例输出 1

5.886349517

样例输入 2

2 2
##
##

样例输出 2

4.000000000