随着时间的推移，人们开始通过记录来保存他们的文明。在石板上，他们刻下了代表他们的村庄、仪式、变迁和历史的数字。

但多年以后，他们发现这些记录的一些部分存在缺陷。为了恢复正确的顺序，他们着手纠正这些错误。

检查他们留下的记录，并恢复失去的历史轨迹。

记录呈现为一个 $N \times N$ 的网格。从上往下数第 $r$ 行、从左往右数第 $c$ 列的单元格记为 $(r, c)$。每一行代表一个 $N$ 位数，从左到右书写，每个单元格中有一个数字。

根据预期的结构，各行的值——当从左到右读作数字时——应该从上到下严格递增。然而，由于抄写错误，一些数字可能被错误地记录了，导致某些行不再遵循这种递增顺序。

为了纠正记录，人们决定从网格中擦除一些数字。他们的目标是确保每一行中剩余数字（从左到右阅读）所组成的数字从最上面一行到最下面一行严格递增。

例如，考虑下图所示的情况：

通过擦除如图所示的六个数字，剩余的数字变为 $[335, 854, 2198, 7356, 26481]$。这些值从一行到下一行严格递增，符合预期。

确定必须擦除的最小数字个数。

输入格式

第一行包含一个整数 $N$ —— 石板的大小。

接下来的 $N$ 行，每行包含一个长度为 $N$ 的数字字符串 $B_{i1}, B_{i2}, \dots, B_{iN}$。$B_{ij}$ 是记录在单元格 $(i, j)$ 中的数字。

数据范围

• $2 \le N \le 2000$
• $1 \le B_{ij} \le 9$ ($1 \le i, j \le N$)

输出格式

输出必须擦除的最小数字个数。

保证总是可以通过擦除零个或多个数字来满足条件。

子任务

• 子任务 1（3 分）：$B_{ij} = 1$ ($1 \le i \le N, 1 \le j \le N$)
• 子任务 2（8 分）：$N \le 4$
• 子任务 3（18 分）：$N \le 15$
• 子任务 4（21 分）：$N \le 100$
• 子任务 5（22 分）：$N \le 500$
• 子任务 6（28 分）：无附加限制。

样例

输入样例 1

5
33645
86541
42198
79356
26481

输出样例 1

6

输入样例 2

3
111
111
111

输出样例 2

3

输入样例 3

8
19283746
85749285
56748236
17846565
77759471
85625624
41837461
23876597

输出样例 3

13