Shinomiya는 함께 걷고 싶어

Shirogane와 Shinomiya는 함께 하교하고 있다. 두 사람은 학교가 있는 $(1,1)$에서 집이 있는 $(N,N)$까지 최대한 오랫동안 함께 걸으려고 한다.

두 사람이 걸을 수 있는 곳은 $N\times N$ 크기의 격자로 주어진다. 위에서 $i$번째 행, 왼쪽에서 $j$번째 열에 있는 칸을 $(i,j)$라고 한다. 각 칸에 적힌 .은 이동할 수 있는 길을, #은 이동할 수 없는 벽을 나타낸다.

두 사람은 다음 규칙을 모두 지키며 이동한다.

• 현재 칸에서 바로 아래, 왼쪽, 오른쪽에 있는 칸으로만 이동할 수 있다. 격자 밖으로 나갈 수 없다.
• 벽으로는 이동할 수 없다.
• 한 번 방문한 칸은 다시 방문할 수 없다.
• 연속한 세 번의 이동 방향이 오른쪽, 아래쪽, 왼쪽이거나 왼쪽, 아래쪽, 오른쪽이어서는 안 된다.

마지막 규칙은 가로로 이동한 직후 한 칸 내려왔을 때 곧바로 반대 가로 방향으로 이동할 수 없다는 뜻이다. 예를 들어 오른쪽, 아래쪽, 왼쪽으로 연속해서 이동하는 것은 금지되지만, 오른쪽, 아래쪽, 아래쪽, 왼쪽으로 이동하는 것은 허용된다. 물론 나머지 규칙도 모두 지켜야 한다.

인접한 칸으로 한 번 이동할 때의 거리는 $1$이다. $(1,1)$에서 출발하여 $(N,N)$에 도착하는 경로 중 가장 긴 경로의 이동 거리를 구하여라. 도착할 수 없다면 $-1$을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 가장 긴 유효한 경로의 이동 거리를 한 줄에 출력한다. 도착할 수 없다면 $-1$을 출력한다. 테스트 케이스가 입력된 순서대로 출력한다.

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