Quantum Computer

Kubitukas built a quantum computer shaped as an $N \times M$ rectangular microchip, with a single light sensor mounted inside it. Data is fed in by firing a laser from outside the chip, aimed perpendicular to one of its four sides, so the beam enters one cell wide and travels in a straight line. The laser may be attached to any empty edge cell that is not a corner: attaching it to the bottom edge fires the beam upward, to the left edge fires it to the right, to the top edge fires it downward, and to the right edge fires it to the left.

Some cells are fully occupied by other components and block the beam. To help the beam reach the sensor, Kubitukas may place at most one mirror on any empty cell. A mirror turns the beam passing through it by $90^\circ$ (you may pick either of the two perpendicular directions), and the beam then keeps travelling in a straight line. The beam must never pass through a blocked cell.

Compute the minimum number of mirrors required for the beam to reach the sensor.

The first line contains two integers $N$ and $M$ — the dimensions of the microchip.

Each of the next $N$ lines contains $M$ characters describing the chip. Character $s_{i,j}$ is one of:

• . — an empty cell that the beam can pass through;
• J — the cell holding the light sensor;
• # — a cell fully blocked by a component; the beam cannot pass through it.

The sensor always lies strictly inside the chip (never on an edge cell).

Print one line:

• 0 if the beam can reach the sensor with no mirror (a straight shot);
• 1 if a mirror is required and exactly one mirror suffices;
• NEPASIEKIAMA if the sensor cannot be reached even with one mirror.

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