github.com/captn3m0/codechef.git

---
{"languages_supported":{"0":"NA"},"title":"N1","category":"NA","old_version":true,"problem_code":"N1","tags":{"0":"NA"},"layout":"problem"}
---

<h3> All submissions for this problem are available. </h3><p>Treasure Hunting is a great computer game that has attracted generations of Bytelandian children.
</p><p>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).
</p><p>Some of the squares are blocked and some of the squares contain treasures.
</p><p>Dave needs to capture all the treasures in the maze before going to square (n,n).
</p><p>In each second, Dave can go to one of its four adjacent squares (if the destination is not blocked). 
</p><p>Find the earliest time that Dave can reach the destination(n,n) after collecting all the treasures in the maze.

<h3>Input</h3>
</p><p>The first line contains t, the number of test cases (about 15). Then t test cases follow. Each test case has the following form.
</p><p>The first line contains N (1 &lt;= N &lt;= 13), the size of the maze
</p><p>The N following lines describe the maze. The meaning of the symbols is as follows:
</p><p>'.' : an empty square
</p><p>'*' : a treasure
</p><p>'#' : a blocked square
</p><p>The number of treasures in the maze does not exceed 13. Squares (1,1) and (n,n) are always empty.
</p><p>Each test case's input is separated by a blank line.

<h3>Output</h3>
</p><p>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.

<h3>Example</h3>

<pre>
<b>Input:</b>
4

3
...
.##
*#.

3
..*
...
...

3
..*
*..
...

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

<b>Output:</b>
-1
4
6
16
</pre></p>