A bank robbery has just happened in city A. The criminals were seen to be escaping in a car. Since city B is the only other city near city A, the criminals may be driving towards city B. The road network connecting the two cities is quite complicated. There are already some sentries at some fixed locations on the roads. The police official in city A wants to send a group of policemen to one of the sentries, where they can examine every passing car carefully.

This special sentry is selected according to two rules: first, it should be a sentry that the criminals must pass in order to go to city B. Second, the shortest driving distance from city A to the sentry should be minimal so that the policemen can reach there as soon as possible.

The police official asks you to help him find this special sentry. He has given you a map for you to work on.

The map is represented by a M*N array of square cells. Each cell may be city, road or mountain. There are only two cities: A and B. They are located at opposite corners of the map. A sentry can only be located on a road cell. There can be at most one sentry on each road cell. A car can only move from a road or city cell to a neighboring road or city cell, and it cannot move out of the map. Two cells are neighboring iff they share a common edge. It is guaranteed that the two cities A and B are connected by the roads.

There are at most 20 test cases. Each case begins with a line containing two integers M,N (1<=M<=100,2<=N<=100). The next M lines are the map. Each line contains N characters. The "#" character stands for mountains, "." for a road cell without a sentry on it, "*" for a road cell with a sentry on it, "A" and "B" for the cities A and B respectively. City A is always at row 1, column 1. City B is always at row M, column N.

A case with M=0, N=0 marks the end of input. This case should not be processed.

2 2
A*
*B
4 6
A.*#..
.#*##*
.#.#.#
#....B
0 0

No solution.
1 3