辽宁舰以中国的一个省份命名，是中国人民解放军海军服役的第一艘航空母舰。它从乌克兰购入时是一艘未完工的船壳，后由中国重建，成为中国蓝水海军计划的重要组成部分。辽宁舰曾多次远航至太平洋，展现了中国捍卫领土完整的力量与决心。

现在，辽宁舰正在大西洋进行演习！海洋上的广阔演习区域可以看作是一个 $n \times n$ 的网格，共有 $n \times n$ 个交叉点。每个交叉点代表演习区域的一个检查点。辽宁舰从坐标为 $(0,0)$ 的左下角检查点出发，目的地是坐标为 $(n-1, n-1)$ 的右上角检查点。$x$ 轴正方向向右，$y$ 轴正方向向上。所有检查点的坐标均为整数。在每次移动中，辽宁舰可以从一个检查点移动到其周围 8 个相邻的检查点之一，每次移动耗时一天。由于天气恶劣，部分检查点无法通行。此外，众所周知，大西洋上存在一个百慕大三角，许多船只和飞机在那里失踪。辽宁舰不能冒险进入该三角区域。当然，辽宁舰也不能离开演习区域。请计算辽宁舰到达目的地所需的最短天数。

输入格式

测试用例不超过 30 组。 对于每组测试用例： 第一行是一个整数 $n$ ($2 \le n \le 20$)，表示演习区域为 $n \times n$ 的网格。 第二行包含六个浮点数 $x_1, y_1, x_2, y_2, x_3, y_3$ ($-100 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 100$)，小数点后最多有 2 位，表示百慕大三角的三个顶点坐标 $(x_1, y_1), (x_2, y_2)$ 和 $(x_3, y_3)$。辽宁舰不能进入该三角形内部，但允许沿其边行走或触碰其顶点。 随后是一个 $n \times n$ 的字符矩阵，由 '.' 和 '#' 组成，表示所有检查点的天气状况。'.' 表示天气良好，'#' 表示天气恶劣。左下角的字符代表检查点 $(0,0)$ 的天气，其右侧的字符代表 $(1,0)$，右上角的字符代表 $(n-1, n-1)$。

保证检查点 $(0,0)$ 不在百慕大三角内部或其边上。

输出格式

对于每组测试用例，输出辽宁舰到达目的地所需的最短天数。如果辽宁舰无法到达目的地，则输出 -1。

样例

样例输入 1

3
0.5 1.5 1.5 1.5 1 0.5
.#.
...
..#

样例输出 1

3

样例输入 2

3
0.5 1.5 1.5 1.5 1 0.5
.#.
..#
..#

样例输出 2

-1