题目描述

$\red{Farmer John }$的奶牛喜欢玩流行游戏"数独"的有趣变体。他们的版本涉及 $\red{3 \times 3 }$子网格的 $\red{9 \times 9 }$网格，就像常规数独一样。但是，奶牛的版本只使用二进制数字：

$\red{000 ~000 ~000}$

$\red{001 ~000 ~100}$

$\red{000 ~000 ~000}$

$\red{000 ~110 ~000}$

$\red{000 ~111 ~000}$

$\red{000 ~000 ~000}$

$\red{000 ~000 ~000}$

$\red{000 ~000 ~000}$

$\red{000 ~000 ~000}$

二进制数独的目标是切换旧能少的位，以便九行中的每一行、九列中的每一列以及九个 $\red{3\times 3 }$子网格中的每一个都具有偶校验（即包含偶数个 $\red{1）}$。对于上面的示例，一组 $\red{3 }$个切换提供 了一个有效的解决方案：

$\red{000 ~000 ~000}$

$\red{001 ~000 ~100}$

$\red{001 ~000 ~100}$

$\red{000 ~110 ~000}$

$\red{000 ~110 ~000}$

$\red{000 ~000 ~000}$

$\red{000 ~000 ~000}$

$\red{000 ~000 ~000}$

$\red{000 ~000 ~000}$

给定二进制数独板的初始状态，请帮助奶牛确定解决它所需的最小切换次数。

给出一个$\red{9*9}$的$\red{01}$矩阵，问最少修改几个数能使每行、每列以及每个九宫格中$\red{1}$的个数均为偶数。

输入格式

第 $\red{1..9 }$行：每行包含一个 $\red{9 }$位二进制字符串，对应于初始游戏板的一行。

输出格式

第 $\red{1 }$行：使每行、列和子网格具有偶数奇偶性所需的最少切换次数。

样例

输入样例

000000000 
001000100 
000000000 
000110000 
000111000 
000000000
000000000
000000000
000000000

输出样例

3

提示

示例输入中的数独板与上面的问题文本中的相同。

三个切换足以解决难题。