Die Kühe von Farmer John spielen gerne eine interessante Variante des beliebten Spiels „Sudoku“. Wie beim normalen Sudoku besteht ihre Version aus einem $9 \times 9$-Gitter mit $3 \times 3$-Teilgittern. Die Version der Kühe verwendet jedoch nur Binärziffern:

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

Das Ziel des binären Sudokus ist, möglichst wenige Bits umzuschalten, sodass jede der neun Zeilen, neun Spalten und neun $3 \times 3$-Teilgitter gerade Parität besitzt (also eine gerade Anzahl von Einsen enthält). Im obigen Beispiel ergeben 3 Umschaltungen eine gültige Lösung:

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

Gegeben ist der Anfangszustand eines binären Sudoku-Gitters. Hilf den Kühen, die zum Lösen erforderliche minimale Anzahl von Umschaltungen zu bestimmen.

Eingabe

• Zeilen $1..9$: jede Zeile enthält eine neunstellige Binärzeichenkette, die einer Zeile des anfänglichen Spielfelds entspricht.

Ausgabe

• Zeile 1: die minimale Anzahl von Umschaltungen, um jeder Zeile, Spalte und jedem Teilgitter gerade Parität zu geben.

Beispiele

Eingabe 1

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

Ausgabe 1

3

Hinweis

Das Sudoku-Gitter in der Beispieleingabe ist dasselbe wie im obigen Aufgabentext.

Drei Umschaltungen genügen, um das Rätsel zu lösen.

Aufgabenautor: Brian Dean