can any one give me the algorithm how to solve the given problem???

Treasure Hunting is a great computer game that has attracted generations of Bytelandian children.

In the game, there is a maze divided into NxN squares. Dave starts in the top-left corner, which is square (1,1), and needs to go to the bottom-right corner, which is square (n,n).

Some of the squares are blocked and some of the squares contain treasures.

Dave needs to capture all the treasures in the maze before going to square (n,n).

In each second, Dave can go to one of its four adjacent squares (if the destination is not blocked).

Find the earliest time that Dave can reach the destination(n,n) after collecting all the treasures in the maze.

Input

The first line contains t, the number of test cases (about 15). Then t test cases follow. Each test case has the following form.

The first line contains N (1 <= N <= 13), the size of the maze

The N following lines describe the maze. The meaning of the symbols is as follows:

‘.’ : an empty square

‘*’ : a treasure

‘#’ : a blocked square

The number of treasures in the maze does not exceed 13. Squares (1,1) and (n,n) are always empty.

Each test case’s input is separated by a blank line.

Output

For each test case, print in a single line the earliest time that Dave can reach the destination after collecting all the treasures. If Dave cannot reach the destination, print -1.

EXAMPLE

input

4

3

…

.##

*#.

3

…*

…

…

3

…*

*…

…

4

…

.#.*

.#*.

**#.

Output:

-1

4

6

16