题目描述

农夫约翰的奶牛喜欢玩“数独”这个流行游戏的有趣变体。

它们的数独在9个3×3的子网格构成的9×9网格内进行，这一点和常规数独一样。

但是奶牛们的版本是只用二进制数字：

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
二进制数独的目标是尽可能少的切换其中的一些数字（0变为1，1变为0），以使每行，每列以及每个3×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行，每行包含一个9位二进制字符串，用来描述数独矩阵。

输出格式

输出解决该问题所需要的最少切换数字数量。

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

3