Background

The problem setter is playing a game called Portal. But because they are not very good at it, they asked you to help them pass a few levels they cannot clear.

What? You say you cannot play?

The player needs to reach the exit using a portal gun. By shooting the portal gun, two kinds of portals can be created: an orange portal and a blue portal. Both sides can be used as an entrance or an exit. When creating a portal, the other portal of the same color will disappear. That is, it is impossible to have two portals of the same color at the same time. At most, one blue portal and one orange portal can exist at the same time.

The two portals create a visual and physical connection between two locations in 3D space. Portals can only be placed on planes, and when the player comes out of a portal, their body will automatically adjust to be level due to gravity.

The problem setter has put all their hopes on you. Oh, right, since the setter likes to get things for free, they are playing a pirated Portal.

Problem Description

On an $n \times n$ 2D grid, use $(x,y)$ to represent the cell at row $x$, column $y$. Each cell is one of wall, void, or ground, represented by #, *, . respectively. The player can only stand on ground. Everything outside the map is wall.

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

After choosing a direction and a color, a portal of that color will be built on the wall face of the first wall hit in that direction, and any previously built portal of the same color will be destroyed. Portals of different colors cannot be built on the same wall face.

The player can move to adjacent empty cells (up, down, left, right). The player can also travel between portals of different colors. If the player moves toward a wall and there is a portal on that wall face, and currently both portals have been built, then the player will come out from the other portal (it must be ensured that the player also stands on ground after coming out).

When coming out, the player will stand on an empty cell outside the other portal, and any of the four directions is allowed.

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

Note: here “use” means how many times you pass through a portal face.

Input Format

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

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

The next $n$ lines each contain $n$ characters, consisting only of #, *, . to describe the map.

Output Format

For each test case, output one number: the minimum number of times the portal gun needs to be used. If it is impossible to reach the destination, output -1. If the start or the end is not ground, then terminate the program immediately.

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

2
2

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

4
2

见下发文件portal1.in

见下发文件portal1.ans

见下发文件portal2.in

见下发文件portal2.ans

Hint

Sample 1 Explanation

We use white cells for empty space, black cells for walls, blue cells for blue portals, and orange cells for orange portals. The first round can be drawn as the following map:

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

The second round is as follows:

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

Constraints

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

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

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

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

Translated by ChatGPT 5