Alle mucche di Farmer John piace giocare a una variante interessante del popolare gioco «Sudoku». La loro versione usa una griglia di $9 \times 9$ con sottogriglie di $3 \times 3$, proprio come il sudoku normale. Tuttavia, la versione delle mucche usa soltanto cifre binarie:

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

Lo scopo del sudoku binario è invertire il minor numero possibile di bit affinché ciascuna delle nove righe, nove colonne e nove sottogriglie di $3 \times 3$ abbia parità pari (cioè contenga un numero pari di $1$). Per l’esempio sopra, un insieme di 3 inversioni dà una soluzione valida:

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

Dato lo stato iniziale di una griglia di sudoku binario, aiuta le mucche a determinare il numero minimo di inversioni necessarie per risolverla.

Input

• Righe $1..9$: ogni riga contiene una stringa binaria di 9 cifre corrispondente a una riga della griglia iniziale.

Output

• Riga 1: il numero minimo di inversioni necessarie affinché ogni riga, colonna e sottogriglia abbia parità pari.

Esempi

Input 1

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

Output 1

3

Note

La griglia di sudoku nell’input di esempio è la stessa del testo del problema sopra.

Tre inversioni sono sufficienti per risolvere il rompicapo.

Autore del problema: Brian Dean