在风暴中被冲到荒岛上的鲁滨逊造了一艘船，以便出海寻找人类的居住地。他是一位经验丰富的船员，因此他按照工艺规则建造了这艘船：它具有纵向对称轴，形状适宜。船头较窄，向船中心逐渐变宽，然后又向船尾逐渐变窄。特别地，在船的某个中间位置，船身比船头和船尾都要宽。

不幸的是，鲁滨逊在极其不合适的地方下水了：周围全是极其茂密的芦苇。而且，芦苇非常坚硬，船无法冲过去。也许鲁滨逊可以通过在芦苇丛中小心地操纵来到达公海。

由于机动性不足，船可以向前、向后甚至向侧面（向左或向右）移动，但不能转向。因此，船在移动时，船尾或侧面朝前是允许的，甚至可能是必要的。

你需要判断鲁滨逊是否能到达公海。

为了简化任务，岛屿及其周边环境将由一张正方形地图表示，地图被划分为单位正方形区域，每个区域要么是水域，要么是鲁滨逊的船的一部分，要么是障碍物（如陆地或芦苇）。初始时，船平行于四个基本方向之一放置，即其纵向对称轴平行于该方向，且该轴平分其所覆盖的单位区域。

我们假设公海从地图边界外开始。因此，如果鲁滨逊的船能够离开地图所描绘的区域，他就能到达公海。单次移动是指将船向选定方向（北、南、东或西）移动到相邻的区域。如果移动前后船都完全处于水域中（即不占据任何包含障碍物的区域），则该移动是允许的。

你需要编写一个程序：

• 从标准输入读取地图描述；
• 计算船完全离开地图区域所需的最少移动次数；
• 将该数字输出到标准输出。

输入格式

第一行包含一个整数 $3 \le n \le 2\,000$，表示地图的边长。接下来的 $n$ 行中，每行包含 $n$ 个字符，描述地图的各个区域：第 $(j+1)$ 行的第 $i$ 个字符表示区域 $(i,j)$ 的内容。可能出现的字符如下：

• "." - （点）表示充满水的区域；
• "X" - 表示障碍物（陆地或芦苇）；
• "r" - 表示鲁滨逊船的一部分。

输出格式

你的程序应在标准输出的第一行（也是唯一一行）输出一个正整数，等于船完全离开地图区域所需的最少移动次数。如果无法到达公海，则输出单词 'NIE'（波兰语中的“不”）。

样例

输入 1

10
..........
..........
..r.......
.rrrX.....
rrrrr.....
.rrr......
X.r.......
.Xr.......
..........
..........

输出 1

10