题目背景

出题人正在玩一款叫 Portal 的游戏。但由于他太菜了，于是找来了你，让你帮他过几个他过不去的关卡。

什么？你说你不会玩？

玩家需要通过传送门枪到达出口。利用传送门枪射击可开出两种门，分别是橙色门和蓝色门，两面都可作入口及出口。在创造门的时候，另一道同样颜色的门会消失，即是说同时间不可能存在两道同色的门，最多只可同时存在一道蓝色及一道橙色的门。

两道传送门在三维空间之中的两个地点创造出视觉上及物理上的连系，传送门的立点只限于平面，玩家从门出来时会自动配合地心吸力调整身体水平。

出题人把所有希望都寄托于你身上了哟。哦，对了，因为出题人是个白嫖党，因此他拥有的是盗版 Portal。

题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

2
2

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

4
2

见下发文件portal1.in

见下发文件portal1.ans

见下发文件portal2.in

见下发文件portal2.ans

提示

样例1解释

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

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

而第二局地图如下：

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

数据范围

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

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

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

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