Problem G
Drive Right

Turning left is possibly one of the most dangerous things you can do while driving. According to federal data, 53.1 percent of crossing-path crashes involve left turns, as opposed to only 5.7 percent involving right turns. Many large shipping companies strongly advise their drivers against turning left, especially on well-trafficked roads ¹.

You have just been hired as a driver for the Above-average Comic Messengers (ACM), a service dedicated to delivering comic books to customers around town. Knowing the dangers of right turns and wishing to impress your bosses, you would like to show them an alternate shipping route that only uses right turns (denote this the “right route” - ie. a route at which you can only go straight or turn right at any intersections). For the sake of simplicity, you assume that roads are all two-way roads, and you get to work mapping routes. Unfortunately, there are too many maps for you to process all of this by hand, so you decide to write a computer program to help you process the data.

Input

Each input file will consist of one test cases. The first line of each test case will contain a two integers $w$ and $h$ ($1 \leq w, h \leq 100$), the width and height of the map you would like to process. The next $h$ lines contain $w$ characters each, forming a grid that represents the map. The map will be made of four characters: “A”, “B”, “X”, and “.”. The starting point of your delivery route will be marked with an “A”, while the ending point will be marked with a “B”. All roads will be marked by the character “.”. You can exit A and you can enter B from any direction, provided that there is adjacent road. All cells on the map through which you cannot drive will be marked by the character “X”.

Note: For the purposes of this problem, a“right turn” corresponds to a movement of your car one square in the grid to the right followed by a 90 degree clockwise rotation of your car. You may only turn at an intersection where you can make a right turn and you cannot turn around on a dime.

Output

For each test case, print a single line containing one integer $l$, the length of the shortest “right route” from A to B. If no right route exists, print -1.

5 5
XXXXA
XXXX.
XXXX.
XXXX.
B....

8

5 5
XXXXB
XXXX.
XXXX.
XXXX.
A....

-1

5 5
XXXBX
XXX.X
XXX.X
A....
XXX..

10