C. Cross Across the Grid
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$N \times N$$$ grid where $$$N$$$ is always odd.

Each cell in this grid contains an uppercase English letter. The grid has concentric layers, and you can think of each layer as a ring. The outermost layer is layer 1, the next one is layer 2, and so on until the center of the grid.

For each layer, you can rotate its contents (clockwise or anticlockwise) for arbitrary times. Each rotation corresponds to shifting the content of the ring by one cell position.

For example, given the following $$$3 \times 3$$$ grid, the center would be X and there is only one layer, define it as layer 1. Starting from the top-left corner of the layer in the clockwise direction, layer 1 would be ABCFKPHD. 

ABC
DXF
HPK

If we rotate layer 1 in the clockwise direction 2 times, the grid will become the following. 

HDA
PXB
KFC

In the rotated grid, HAXKC are on the diagonals while others do not.

Your task is to determine the minimum number of rotations to make the two diagonals of the grid (forming an X shape) have the same character. It is guaranteed the solution always exists with the given input.

Input

The first line contains a single integer, $$$N$$$, the dimension of the grid ($$$1 \le N \le 100$$$, $$$N$$$ is odd).

The next $$$N$$$ lines each contain $$$N$$$ characters (without spaces between them), representing the $$$N \times N$$$ grid.

Output

Output a single integer, the minimum number of rotations required to make the two diagonals of the grid have the same character in each cell.

Examples
Input
5
TYEKL
RDEBP
EEEEE
XHEFY
YUEWD
Output
3
Input
9
NMJIITCUS
LXRQWKIXL
UIIKXDIHV
UBTFITYDO
IXKIIILSI
ABCSIPMLJ
YYIFIFIIM
CKINGHZGY
JELGIUBYY
Output
6
Note

In the first example, the minimum number of rotations needed will be rotating layer 1 in the anti-clockwise direction 2 times and rotating layer 2 in the clockwise direction 1 time.