This question has been prepared by our sponsor JotForm.

Cem goes to buy some bread every morning. He really likes hot bread. His family wants him to bring the loaves of bread to the home as soon as possible to eat the loaves of bread with good menemen. So, let's help him to go home as quickly as possible.

The neighbourhood Cem lives in is represented as an \(\textbf{N x M}\) grid. The grid consists of only the characters #, ., A, B. # characters represent walls that Cem cannot pass through. . characters represent open roads that Cem can move on. A is Cem's current position, he just bought the hot bread and waiting in the bakery. Finally, B is Cem's home. Can you find the minimum distance that Cem needs to travel, in order to reach home as quickly as possible?

The cells on the border will be walls #. There will be only one A and only one B in each input. Cem may not reach his home every time, you should print -1 in such cases.

Input

The initial line only includes \(\mathbf{N}\) and \(\mathbf{M}\).

In the next \(\mathbf{N}\) lines, there exists a grid with \(\mathbf{N}\) rows and \(\mathbf{M}\) columns.

• \(1 \leq \mathbf{N}, \mathbf{M} \leq 10^{3}\)

Output

In a single line, print the minimum distance between Cem and his home. If B is not accessible from A print -1 instead.

Examples

Input:

7 5
#####
#A..#
###.#
#...#
#.###
#..B#
#####

Output:

10

Input:

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

Output:

6