题目描述

农夫约翰的奶牛们喜欢玩一款有趣的“数独”变体游戏。这款游戏和标准数独一样，包含一个 $9 \times 9$ 的网格，且网格被划分为 $3 \times 3$ 的子网格。不过，奶牛们的版本只使用二进制数字（$0$ 和 $1$）：

000 000 000
001 000 100
000 000 000
000 110 000
000 111 000
000 000 000
000 000 000
000 000 000
000 000 000

二进制数独的目标是尽可能少地翻转比特位，使得九行中的每一行、九列中的每一列，以及九个 $3 \times 3$ 子网格中的每一个都具有偶校验（即包含偶数个 $1$）。对于上面的示例，只需 $3$ 次翻转就能得到一个有效的解：

000 000 000
001 000 100
001 000 100
000 110 000
000 110 000
000 000 000
000 000 000
000 000 000
000 000 000

给定二进制数独棋盘的初始状态，请帮助奶牛们确定解决该问题所需的最少翻转次数。

【简化题意】

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

输入格式

第 $1$ 至 $9$ 行：每行包含一个 $9$ 位的二进制字符串，对应初始棋盘的一行。

输出格式

第 $1$ 行：一个整数，表示使每一行、每一列和每一个子网格都具有偶校验所需的最少翻转次数。

000000000 
001000100 
000000000 
000110000 
000111000 
000000000 
000000000 
000000000 
000000000 

3 

提示

样例输入中的数独棋盘与题目描述中的示例一致。

三次翻转即可解决该谜题。