Sometimes an open field could be as much of a maze as narrow tunnels. Given an obstacle in an otherwise empty room, what is the shortest path around it?

The input file DATA4.txt will contain five sets of data, each a 8 by 8 character map. The character representations are as follows:

• . - empty space
• # - wall
• A - start
• B - end

The output file OUT4.txt will contain five lines -- each the shortest integer distance between A and B.

Notes: There will always be a valid path. Valid steps are into any adjacent empty space; diagonal steps are valid. Refer to sample data for examples.

........
....#...
....#...
A...#..B
....#...
....#...
........
........
......#.
......#.
......#.
......#.
A..####B
..#.....
.##.....
.##.....
		        

7
7