Krowy Farmer John lubią grać w ciekawą odmianę popularnej gry „Sudoku”. Ich wersja, podobnie jak zwykłe sudoku, używa siatki $9 \times 9$ z podsiatkami $3 \times 3$. Wersja krów korzysta jednak tylko z cyfr binarnych:
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
Celem binarnego sudoku jest zmiana jak najmniejszej liczby bitów, tak aby każdy z dziewięciu wierszy, dziewięciu kolumn i dziewięciu podsiatek $3 \times 3$ miał parzystą parzystość (czyli zawierał parzystą liczbę jedynek). Dla powyższego przykładu zestaw 3 zmian daje poprawne rozwiązanie:
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
Mając początkowy stan planszy binarnego sudoku, pomóż krowom ustalić minimalną liczbę zmian bitów potrzebną do jego rozwiązania.
Wejście
- Wiersze $1..9$: każdy wiersz zawiera 9-cyfrowy napis binarny odpowiadający jednemu wierszowi początkowej planszy.
Wyjście
- Wiersz 1: minimalna liczba zmian bitów potrzebna, aby każdy wiersz, kolumna i podsiatka miały parzystą parzystość.
Przykład
Wejście 1
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000
Wyjście 1
3
Uwagi
Plansza sudoku w przykładowym wejściu jest taka sama jak w powyższym tekście zadania.
Trzy zmiany bitów wystarczą, aby rozwiązać łamigłówkę.
Autor zadania: Brian Dean