Mazes

Description

Given an $n$ by $n$ maze, find the shortest path from the start (which is at the top), to the end (which is at the bottom). A period represents a clear space and a hashtag represents an impassable wall. In a single step, you may go in any of the 4 cardinal directions. You may also assume that the top row and the bottom row have only one open space each. You may also assume that every maze has a solution.

Input

The first line of input contains an integer $N$, denoting the number of test cases. $N$ test cases follow. Each test case begins with a line containing an integer $n$. $n$ lines follow, describing the maze.

Output

For each test case, print a line containing the length of the shortest path to the exit.

Sample Input

2
17
#.###############
#.##....#...#...#
#.##.###..#.#.#.#
#.##.##.###...#.#
#....###...####.#
####.....#......#
###############.#
#...............#
#.###############
#...............#
########.######.#
#........#......#
#.#############.#
#.............#.#
#############.#.#
#...............#
#.###############
7
###.###
.......
.......
.......
.......
.......
###.###

Sample Output

74
6