뱀 게임

미르코가 유명한 컴퓨터 게임 Snake를 흉내 낸 게임을 만들고 있다. 이 게임에서는 크기가 $R \times S$ 픽셀인 화면 위에서 뱀을 움직여 사과를 모두 먹어야 한다.

미르코가 만든 게임은 원작과 규칙이 다르다.

• 사과는 무작위로 나타나지 않는다. 게임을 시작할 때 모든 사과의 위치를 이미 알고 있다.
• 게임이 시작되면 뱀은 화면의 왼쪽 아래 픽셀에 있고, 오른쪽을 보고 있다.
• 버튼은 A와 B 두 개다.
• A를 누르면 뱀이 지금 보고 있는 방향으로 1픽셀 전진한다. 그 이동이 화면 밖으로 나가는 이동이면 아무 일도 일어나지 않는다.
• B를 누르면 뱀이 위로 1픽셀 이동하고, 보고 있는 방향이 180도 바뀐다.
• 뱀이 사과가 있는 픽셀로 이동하면 그 사과를 먹는다. 원작과 달리 몸은 길어지지 않는다.

사과의 처음 위치가 주어질 때, 뱀이 사과를 모두 먹으려면 버튼을 최소 몇 번 눌러야 하는지 구하여라.

첫째 줄에 화면의 높이 $R$과 너비 $S$가 주어진다. ($2 \le R, S \le 1000$)

다음 $R$개 줄에는 화면의 상태가 각각 정확히 $S$개의 문자로 주어진다. 사과가 있는 픽셀은 'J', 빈 픽셀은 '.'이다. 이 중 첫 줄이 화면의 맨 윗줄이다.

화면의 왼쪽 아래 칸에는 뱀의 처음 위치를 나타내는 'Z'가 있다. 화면에 사과가 하나도 없을 수도 있다.

모든 사과를 먹는 데 필요한 최소 버튼 입력 횟수를 한 줄에 출력한다.

첫 번째 예제에서 사과를 모두 먹는 가장 짧은 버튼 입력은 BBAAABB이다.