Farmer John の牛たちは、人気のゲーム「数独」の面白い変種で遊ぶのが好きです。普通の数独と同様に、$3 \times 3$ の小領域からなる $9 \times 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
二進数独の目標は、できるだけ少ないビットを反転して、9 本の行、9 本の列、9 個の $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
二進数独の盤面の初期状態が与えられます。解くために必要な最小の反転回数を牛たちが求めるのを手伝ってください。
入力
- $1..9$ 行目：各行は初期盤面の 1 行に対応する 9 桁の二進文字列です。
出力
- 1 行目：すべての行、列、小領域を偶数パリティにするために必要な最小の反転回数。
入出力例
入力 1
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000
出力 1
3
注記
入力例の数独の盤面は、上の問題文に示したものと同じです。
3 回の反転でパズルを解けます。
問題作成：Brian Dean