题目描述

题目译自 XV OI Olimpiada Informatyczna – I etap Robinson

荒岛及周围被划分为 $n \times n$ 的正方形网格，格子类型包括水域（.）、障碍（X）、小船部分（r）。小船满足以下条件：

1. 平行于四个基本方向之一（上下左右朝向）；
2. 沿纵轴对称，且中心纵轴穿过一列方格；
3. 形状为“船首窄、中部宽、船尾窄”，中间某处宽度超过首尾。

小船仅能沿北、南、东、西方向整体移动一格，移动前后需完全位于水域（非障碍、非网格外）。目标是判断小船能否完全驶出网格（整体离开网格区域），并计算最少移动次数；若无法驶出，输出“NIE”。

输入格式

1. 第一行：整数 $n$（网格边长，$3 \leq n \leq 2000$）；
2. 接下来 $n$ 行：每行 $n$ 个字符，描述网格中每个方格的类型（.、X、r）。

输出格式

输出一行，若能驶出则输出最少移动次数，否则输出“NIE”。

样例

输入

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

输出

10

样例解析

小船初始位置在网格中部，通过 10 次连续移动（如逐步向西），最终整体离开网格，达到开放海域。