米哈伊尔决定学习如何下广义国际象棋。为此，他准备了一个大小为 $n \times n$ 的棋盘格。位于第 $i$ 行第 $j$ 列交叉处的格子被涂上颜色 $a_{ij}$。
米哈伊尔是初学者，可能会将棋盘涂错。因此，棋盘上的一些格子可能需要重新涂色。如果满足以下两个条件，则认为棋盘涂色正确：
- 棋盘上的格子使用的不同颜色不超过两种。
- 没有相邻（共享一条边）的格子涂有相同的颜色。
米哈伊尔意识到在大的棋盘上下棋对他来说太难了。因此，他可能从自己的棋盘中裁出一个较小的棋盘，只保留前 $r$ 行和前 $c$ 列组成的矩形区域，并仅将这个区域正确涂色。 对于每一对数 $(r, c)$，其中 $1 \le r \le n$ 且 $1 \le c \le n$，计算值 $b_{rc}$——为了使前 $r$ 行和前 $c$ 列的矩形区域涂色正确，需要重新涂色的格子的最小数量。
输入格式
第一行包含一个整数 $n$（$1 \le n \le 400$）——棋盘的大小。 接下来的 $n$ 行描述棋盘。其中第 $i$ 行包含 $n$ 个整数 $a_{i1}, \dots, a_{in}$（$1 \le a_{ij} \le 10^9$）——第 $i$ 行格子的颜色。
输出格式
输出 $n$ 行，其中第 $i$ 行应包含 $n$ 个整数 $b_{i1}, \dots, b_{in}$。
子任务
| 子任务 | 分数 | 额外限制条件 | |
|---|---|---|---|
| 1 | 11 | $n \le 50$ | |
| 2 | 22 | $n \le 200$ | |
| 3 | 8 | $a_{ij} \le 2$ | |
| 4 | 17 | $a_{ij} \le 10$ | |
| 5 | 15 | $a_{ij} \le 100$ | |
| 6 | 7 | $a_{ij} \le 10^4$ | |
| 7 | 20 | - |
样例
输入 1
2 7 7 7 7
输出 1
0 1 1 2
输入 2
3 1 1 2 2 4 4 3 1 2
输出 2
0 1 1 0 2 4 1 3 5