Robinson

Tossed by a storm onto a deserted island, Robinson built himself a boat so he could put out to sea and search for a place where people live. As an experienced sailor he shaped it properly: the boat has a longitudinal axis of symmetry, its bow is thin, it widens gradually toward the middle, and then narrows again toward the stern. In particular, somewhere in the middle the boat is wider than at either the bow or the stern.

Unfortunately, Robinson launched the boat in a very poor spot: it is surrounded by extremely thick, stiff reed that the boat cannot break through. Perhaps he can still reach the open sea by carefully steering between the reed.

The boat has poor maneuverability. It can move forward, backward, and sideways (left or right), but it cannot turn. So, when needed, it may move stern-first or broadside-first rather than bow-first.

Decide whether Robinson can reach the open sea.

To make the task easier, the island and its surroundings are given as a square map divided into unit square cells, each holding water, part of Robinson's boat, or an obstacle (land or reed). Initially the boat is aligned with one of the cardinal directions: its longitudinal axis of symmetry is parallel to that direction and passes through the centers of the cells the boat covers.

The open sea begins where the map ends, so Robinson reaches the open sea exactly when his boat has completely left the mapped area. In one move the boat is shifted by one cell in a chosen direction (north, south, east, or west). A move is allowed only if, both before and after it, the boat lies entirely on water, that is, it never covers a cell containing an obstacle. Cells outside the map count as open water.

Write a program that reads the map from standard input, computes the minimum number of moves needed for the boat to leave the mapped area completely, and prints that number.

The first line contains one integer $n$ ($3 \le n \le 2000$), the side length of the map. Each of the following $n$ lines contains $n$ characters describing the cells of one row of the map. Each character is one of:

• . — a water cell,
• X — an obstacle (land or reed),
• r — a cell occupied by part of Robinson's boat.

Print, on a single line, the minimum number of moves needed for the boat to leave the mapped area completely. If it is impossible for the boat to reach the open sea, print the word NIE instead.