Mikhail decided to learn how to play generalized chess. For this, he prepared a chessboard of size $n \times n$ cells. Each cell at the intersection of row $i$ and column $j$ is colored with color $a_{ij}$.

Mikhail is a beginner player and might have colored the board incorrectly. Therefore, some cells on the board may need to be repainted. The board is considered correctly colored if two conditions are met:

• The cells on the board are colored with no more than two distinct colors.
• There are no adjacent cells (sharing a side) colored with the same color.

Mikhail realized that playing on a large board would be too difficult for him. Therefore, he might cut out a smaller board from his board, leaving a rectangular area consisting of the first $r$ rows and the first $c$ columns, and color only this area correctly. For each pair of numbers $(r, c)$ where $1 \le r \le n$ and $1 \le c \le n$, calculate the value $b_{rc}$ - the minimum number of cells that need to be repainted so that the rectangular area of the first $r$ rows and the first $c$ columns is colored correctly.

Input

The first line contains an integer $n$ ($1 \le n \le 400$) - the size of the board. The next $n$ lines describe the board. The $i$-th of these lines contains $n$ integers $a_{i1}, \dots, a_{in}$ ($1 \le a_{ij} \le 10^9$) - the colors of the cells in the $i$-th row.

Output

Output $n$ lines, where the $i$-th line should contain $n$ integers $b_{i1}, \dots, b_{in}$.

Subtasks

Examples

Input 1

2
7 7
7 7

Output 1

0 1
1 2

Input 2

3
1 1 2
2 4 4
3 1 2

Output 2

0 1 1
0 2 4
1 3 5