Shinomiya Wants to Walk Together

Shirogane and Shinomiya are walking home together. They want to spend as long as possible walking from their school at $(1,1)$ to their home at $(N,N)$.

The area is represented by an $N\times N$ grid. Cell $(i,j)$ is in the $i$-th row from the top and the $j$-th column from the left. A . represents a passable cell, and a # represents a wall.

They must follow all of these rules:

• Each move goes to the cell immediately below, to the left, or to the right of the current cell. They cannot leave the grid.
• They cannot enter a wall.
• They cannot visit a cell more than once.
• The directions of three consecutive moves cannot be right, down, left, or left, down, right.

The last rule means that, after a horizontal move followed immediately by one downward move, they cannot immediately move horizontally in the opposite direction. For example, right, down, left is forbidden, while right, down, down, left is allowed, provided that the other rules are also satisfied.

Each move to an adjacent cell has distance $1$. Find the distance of the longest valid path from $(1,1)$ to $(N,N)$. If no such path exists, output $-1$.

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, output the distance of the longest valid path on a separate line. If the destination is unreachable, output $-1$. Output the answers in the order the test cases appear in the input.

• $1\leq T\leq 1000$.
• $2\leq N\leq 2000$.
• $|G_i|=N$ ().