Problem Background

The problem setter is playing a game called Portal. However, since he is not skilled enough, he has sought your help to get through some levels he cannot pass.

What? You say you don't know how to play?

The player needs to reach the exit using a portal gun. The portal gun can create two types of doors: orange and blue, both of which can serve as entrances and exits. When creating a door, the previously created door of the same color disappears, meaning at any time, there cannot be two doors of the same color, and at most, there can be one blue and one orange door simultaneously.

The two portals create a visual and physical connection between two locations in a three-dimensional space. The standing point of the portal is limited to a plane, and when the player exits the portal, their body will automatically adjust to the gravity.

The problem setter has placed all his hopes on you. Oh, by the way, since the problem setter is a freeloader, he owns a pirated version of Portal.

Problem Description

On a 2D plane map of size $n \times n$, coordinates are represented as $(x, y)$, indicating the $x$-th row and $y$-th column. Each point is either a wall, void, or ground, denoted by #, *, and ., respectively. The player can only stand on the ground. The area outside the map is considered a wall.

You have a portal gun that can shoot blue and orange portals, which can be used in the four directions: up, down, left, and right.

After selecting a direction and color, a portal of the selected color will be created on the first wall encountered in that direction, and any previously created portal of that color will be destroyed. Two portals of different colors cannot be created on the same wall.

The player can move in the four directions: up, down, left, and right, to empty spaces. The player can also travel between portals of different colors. If the player moves towards a wall that has a portal and two portals are already established, they will exit from the other portal (ensuring they land on the ground).

Upon exiting, the player will be on the empty space outside the other portal, in any of the four directions.

Initially, the player is at $(1,1)$, and the destination is $(n,n)$. Determine the minimum number of times the portal gun needs to be used to reach the destination.

Note that the usage here refers to the number of portal surfaces crossed.

Input and Output Formats

Input Format

The first line contains a positive integer $T$ representing the number of test cases.

For each test case, the first line contains a positive integer $n$ representing the number of rows and columns of the plane map.

The next $n$ lines, each containing $n$ characters, include only #, *, and ., representing the map.

Output Format

For each test case, output a number representing the minimum number of times the portal gun needs to be used. If it is impossible to reach the destination, output -1. If the starting or ending point is not on the ground, terminate the program immediately.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
2

Sample Input #2

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

Sample Output #2

4
2

Sample Input #3

See the file portal1.in

Sample Output #3

See the file portal1.ans

Sample Input #4

See the file portal2.in

Sample Output #4

See the file portal2.ans

Notes

Sample 1 Explanation

We use white squares to represent empty spaces, black squares to represent walls, blue squares to represent blue portals, and orange squares to represent orange portals. The first map can be visualized as follows:

Walk to the orange portal, enter through the orange portal, and exit through the blue portal.

The second map is as follows:

Walk to the blue portal, enter through the blue portal, and exit through the orange portal.

Data Range

For $20\%$ of the data, $n \le 10$.

For $60\%$ of the data, $n \le 100$.

For another $10\%$ of the data, $T=1$ and there is no void.

For $100\%$ of the data, $2 \le n \le 500$, $1 \le T \le 10$.

见题面 Input 部分

见题面 Output 部分