Help Molly evaluate the cost of digging a tunnel from point A to point B, taking advantage of existing tunnels. Digging is hard work, even for a mole, so minimizing the amount of digging is really important for Molly.

A map of the underground is available in the form of a grid of open cells and closed cells. Each open cell represents a section of an existing tunnel and each closed cell represents a section of compact underground soil. The points A and B are also marked in the map. The map can be traversed in the horizontal direction, vertical direction and both diagonal directions.

Assume that:

• A is an open cell;
• B is a closed cell;
• the cost of entering an open cell is zero units;
• the cost of entering a closed cell is one unit.

Write a program that, given a map of the underground, where the points A and B are marked, computes the minimum cost of digging a tunnel from A to B.

Input

The first input line contains two integers, n and m, separated by a single space:

• n (2 <= n <= 300) is the number of lines in the map;
• m (2 <= m <= 300) is the number of characters per line in the map.

The following n lines, each with m characters, contain the following valid character values:

• # - closed cell;
• . - open cell;
• A - the point from where Molly starts digging;
• B - the point Molly intends to reach.

The output contains a single non-negative integer, which represents the minimum cost of digging a tunnel from A to B.

Sample Input

30 70
######################################################################
#.A...################################################################
######################################################################
######################################################################
######################################################################
##................................................................####
######################################################################
######################################################################
##########.###########################################################
###########.##########################################################
############.####################.......###.......###.#####.##########
#############.###################.#########.#####.###.#####.##########
##############.##################.#########.#####.###..####.##########
###############.#################.#########.#####.###.#.###.##########
################.################.#########.......###.##.##.##########
#################.###############.#########.#########.###.#.##########
##################.##############.#########.#########.####..##########
###################.#############.#########.#########.#####.##########
####################.############.......###.#########.#####.##########
#####################.################################################
######################.###############################################
#######################.##############################################
########################.#############################################
#########################.############################################
######################################################################
######################################################################
#####..............................................................###
######################################################################
#################################################################B####
######################################################################

9