You are a CPC member attending SPAR, and you have begun to hit a wall with your problemsolving. To rectify this, you need your regular hit of sugar and caffeine - a Pepsi. However, due to capacity and people not reacting to the Discord announcement, the event has been scheduled in the backrooms in an ancient university building, and the Pepsis are locating in a different room in this mazelike structure.

You and the Pepsi start somewhere on a 2D grid. Every turn you can take 1 step either up, down, left, or right, provided you stay within the confines of the grid and do not walk into a wall. Can you navigate to the Pepsis in the minimum number of steps, or will you take the L on this SPAR?

Input

The first line contains two integers, ~n,m\ (1 \leq n,m \leq 100)~, the height and width of the university building grid.

The next ~n~ lines each contain ~m~ characters: either '@' (you), 'p' (the Pepsi goal), '.' (empty space), or '#' (a wall). It is guaranteed that there will be one '@' and one 'p'.

Output

Output the minimum number of steps required to reach the Pepsi. If it is impossible to reach the Pepsi, output -1. You'll probably get 0 solves in the SPAR...

Example

Input 1

5 5
#####
#p..#
###.#
###.#
@...#

Output 1

8

You can reach the Pepsi in 9 steps by taking 3 steps right, 3 steps up, and 2 steps left.

Input 2

5 5
.@..#
.##.#
.#.##
#p.##
.....

Output 2

-1

There is no way of making it from '@' (your starting point) to 'p' (the Pepsi destination) by only stepping up, down, left, or right.