E. Easy Problem
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Now you have an $$$n \times n$$$ map. It contains obstacles '$$$*$$$', space '$$$.$$$', playerA '$$$a$$$', playerB '$$$b$$$'.

You can control two players to move up, down, left or right at the same time. For example, now $$$A$$$ and $$$B$$$ are in $$$(x_a,y_a)$$$ and $$$(x_b, y_b)$$$, next time the two players can go to:

  • $$$(x_a, y_a+1)$$$ and $$$(x_b, y_b+1)$$$
  • $$$(x_a, y_a-1)$$$ and $$$(x_b, y_b-1)$$$
  • $$$(x_a+1, y_a)$$$ and $$$(x_b+1, y_b)$$$
  • $$$(x_a-1, y_a)$$$ and $$$(x_b-1, y_b)$$$

Note that if the next location is a boundary or obstacle the player will not move.

You need to find the minimum number of steps when two players can meet.

Input

The first line contains one integer $$$n$$$ $$$(2\leq n \leq 50)$$$.

For the next $$$n$$$ lines, each line contains a string of length $$$n$$$.

Output

If in any case, the two players do not meet, print "no solution" in one line.

Otherwise, output the minimum number of steps.

Examples
Input
6
.a....
*.....
......
..b*..
..**..
......
Output
4
Input
4
a*..
*...
....
...b
Output
no solution
Input
4
.ab.
....
....
....
Output
2
Input
7
..a.b..
.......
.......
.......
.......
.......
.......
Output
4