As vacas de Farmer John gostam de jogar uma variante interessante do popular jogo «Sudoku». A sua versão utiliza uma grelha de $9 \times 9$ com subgrelhas de $3 \times 3$, tal como o sudoku normal. No entanto, a versão das vacas usa apenas dígitos binários:

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

O objetivo do sudoku binário é inverter o menor número possível de bits para que cada uma das nove linhas, nove colunas e nove subgrelhas de $3 \times 3$ tenha paridade par (isto é, contenha um número par de uns). Para o exemplo acima, um conjunto de 3 inversões dá uma solução válida:

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

Dado o estado inicial de um tabuleiro de sudoku binário, ajude as vacas a determinar o número mínimo de inversões necessárias para o resolver.

Entrada

• Linhas $1..9$: cada linha contém uma cadeia binária de 9 dígitos correspondente a uma linha do tabuleiro inicial.

Saída

• Linha 1: o número mínimo de inversões necessárias para que cada linha, coluna e subgrelha tenha paridade par.

Exemplos

Entrada 1

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

Saída 1

3

Note

O tabuleiro de sudoku da entrada de exemplo é o mesmo apresentado no texto do problema acima.

Três inversões bastam para resolver o puzzle.

Autor do problema: Brian Dean