题目描述

小达在玩一款双人冒险游戏，在游戏过程中，小达的队友被困在了一个陷阱里面，现在小达要立刻过去营救队友，但是小达被一个 $n*n$ 迷宫拦截，迷宫包括 "*" 和 '.' ，其中 "." 表示空地，"*" 表示墙，遇到墙的时候小达可以绕过去或者花费4秒的时间破开墙（墙被破开之后，再次经过时墙会复原）。每次移动可以往上下左右四个方向（不能移动到迷宫之外），需要花费1秒的时间（移动到墙的位置总共需要5秒）

小达的位置在 $(1,1)$ ，小达的队友被困在 $(n,n)$ 的位置，请帮小达求出最短多长时间能够到达队友的位置开始营救。

输入格式

第一行包含一个整数 $n$ ，表示一个 $n*n$ 的迷宫。

接下来 $n$ 行，每行 $n$ 个字母，表示当前位置为墙或者空地（"*" 表示墙，"." 表示空地），保证 $(1,1)$ 和 $(n,n)$ 的位置为空地。

输出格式

输出最短时间。

5
.....
*.**.
..*..
.*.**
.....

10

数据范围

$1 \leq n \leq 100$