양자 컴퓨터

쿠비투카스(Kubitukas)는 $N \times M$ 크기의 직사각형 마이크로칩으로 이루어진 양자 컴퓨터를 만들었고, 그 내부에는 빛 감지기가 하나 설치되어 있습니다. 데이터는 칩 바깥에서 네 변 중 하나에 수직으로 레이저를 쏘아 입력하며, 이때 빛줄기는 한 칸 폭으로 칩 안으로 들어가 직선으로 나아갑니다. 레이저는 모서리(꼭짓점)가 아닌 비어 있는 가장자리 칸에만 설치할 수 있습니다. 아래 변에 설치하면 빛줄기가 위쪽으로, 왼쪽 변에 설치하면 오른쪽으로, 위쪽 변에 설치하면 아래쪽으로, 오른쪽 변에 설치하면 왼쪽으로 발사됩니다.

일부 칸은 다른 부품이 완전히 차지하고 있어 빛줄기를 막습니다. 빛줄기가 감지기에 닿도록 돕기 위해, 쿠비투카스는 비어 있는 아무 칸에나 거울을 최대 한 개 놓을 수 있습니다. 거울은 그곳을 지나는 빛줄기를 $90^\circ$ 꺾으며(수직인 두 방향 중 원하는 쪽을 고를 수 있습니다), 이후 빛줄기는 다시 직선으로 나아갑니다. 빛줄기는 막힌 칸을 절대 지날 수 없습니다.

빛줄기가 감지기에 닿기 위해 필요한 거울의 최소 개수를 구하세요.

첫째 줄에 마이크로칩의 크기 $N$과 $M$이 주어집니다.

이어지는 $N$개의 줄에는 각각 칩을 나타내는 $M$개의 문자 $s_{i,j}$가 주어집니다.

• . — 빈 칸으로, 빛줄기가 지날 수 있습니다;
• J — 빛 감지기가 있는 칸입니다;
• # — 부품이 완전히 막고 있는 칸으로, 빛줄기가 지날 수 없습니다.

감지기는 항상 칩의 내부에 있으며, 가장자리 칸에는 놓이지 않습니다.

한 줄을 출력합니다.

• 거울 없이 (직선으로) 감지기에 닿을 수 있으면 0;
• 거울 없이는 불가능하지만 거울 한 개로 닿을 수 있으면 1;
• 거울을 한 개 써도 감지기에 닿을 수 없으면 NEPASIEKIAMA.

• $3 \le N, M \le 500$