Description

在一个 $n \times n$ 的二维平面图上，用 $(x,y)$ 表示地图第 $x$ 行第 $y$ 列。每个点都是墙、虚空和地面中的一种，分别用 #，*，. 表示。玩家只能站在地面上。地图之外都是墙。

你手里有一个传送门枪，可以发射蓝色和橙色的传送门，只能朝上下左右四个方向使用。

在选定一个方向和颜色后，将会在该方向上第一个碰到的墙的墙面上建造选定颜色的传送门，并摧毁之前建造的这种颜色的传送门。两种颜色的传送门不能被建立在同一墙面。

玩家可以朝上下左右四个方向的空地移动。玩家还可以在不同色传送门之间穿梭。假如玩家朝一堵墙移动并且墙面上有传送门，并且当前已经建立了两个传送门，那么会从另一个传送门出来（必须保证出来也站在陆地上）。

出来的时候，玩家会站在另一个门外的空地上，四个方向都可以。

一开始玩家站在 $(1,1)$，目的地是 $(n,n)$。求最少使用多少次传送门枪才能到达目的地。

注意哦，这里的使用指的是穿过多少面传送门。

Input Format

第一行一个正整数 $T$ 表示数据组数。

每组数据第一行一个正整数 $n$ 表示平面图的行数和列数。

接下来 $n$ 行每行 $n$ 个字符只包含 #，*，. 三种字符表示地图。

Output Format

对于每组数据输出一个数表示最少需要使用传送门枪的次数。无法到达输出 -1。如果起点或终点不为陆地，那么直接结束程序。

2
5
..###
#.#.#
#..##
...#.
.###.
5
..#..
##..#
#.#..
..#..
.#...

2
2

4
5
...*.
*##*.
#..*.
#*###
.....
5
.#*..
.**.#
###.*
***.*
**...
5
.**..
***.#
###.*
***.*
*****
5
.**..
***.#
###..
***.*
***..

4
2

见下发文件portal1.in

见下发文件portal1.ans

见下发文件portal2.in

见下发文件portal2.ans

Hint

样例1解释

我们用白色格子表示空地，黑色格子表示墙，蓝色格子表示蓝色传送门，橙色格子表示橙色传送门，可以画出第一局的如下地图：

走到橙色传送门处，从橙色传送门进入，蓝色传送门出即可。

而第二局地图如下：

走到蓝色传送门处，从蓝色传送门进入，橙色传送门出即可。

数据范围

对于 $20\%$ 的数据，$n \le 10$。

对于 $60\%$ 的数据，$n \le 100$。

对于另外 $10\%$ 的数据，$T=1$ 且不存在虚空。

对于 $100\%$ 的数据，$2 \le n \le 500$，$1 \le T \le 10$。