有一个 $ n × n $ 的网格。小火龙在起点 $ S (1,1) $ 处，终点在 $ F (n,n) $ 处，除起点和终点外的格子都会有一个数字 $ 0 $ 或 $ 1 $ 。小火龙从起点开始沿着相邻的格子往终点走，且他走的所有格子只能有一种数字（只有 $ 0 $ 或只有 $ 1 $ ）。注意：小火龙只能更改与起点或终点相邻格子的数字。

请问怎样才使得小火龙不可能走到终点？输出最少的更改次数。

题目输入保证一开始的时候存在一条全部是 $0$ 或者全部是$1$的通路

• 注意：如果与起点（或终点）相邻的两个格子上的数字是相同的，则从这两个格子出发都满足有一条全部数字都相同的路径

输入格式

第一行包含一个整数 $ n $ （ $ 3 \leq n \leq 200 $ ）。 

之后 $ n $ 行包含一个网格。 

输出格式

输出一个整数 $ c $ （ $ 0 \leq c \leq 2 $ ）-更改数字的格子数量。 

样例输入

4
S010
0001
1000
111F

样例输出

1

样例输入2

3
S10
111
01F

样例输出2

2

提示

子任务一： $ 30 $ 分，满足 $ 3≤n≤10 $ ；

子任务二： $ 30 $ 分，满足 $ 3≤n≤50 $ ；

子任务三： $ 40 $ 分，满足 $ 3≤n≤200 $ 。

第一个样例中可以选择更改 $ (3,4) $ ，更改后可能为：

S010

0001

1001

111F

第二个样例中可以选择更改 $ (1,2) $ 和 $ (2,1) $ ，更改后可能为：

S00

011

01F