Binary Sudoku Parity Correction

Farmer John's cows play a variant of Sudoku on a 9×9 board divided into 3×3 subgrids. However, this puzzle uses only binary digits (0 and 1). The initial board is given as a 9×9 matrix of 0's and 1's. The objective is to toggle (flip) as few bits as possible so that each of the 9 rows, 9 columns, and 9 subgrids contains an even number of ones.

Toggling a cell changes its value from 0 to 1 or from 1 to 0. Mathematically, if we denote the initial value at cell \((i,j)\) as \(a_{i,j}\) and define \(x_{i,j}=1\) if cell \((i,j)\) is toggled (and 0 otherwise), then the final value of cell \((i,j)\) is \(a_{i,j}+x_{i,j}\) modulo 2. The parity conditions to satisfy are:

[ \text{For each row } i: \quad \left(\sum_{j=0}^{8} a_{i,j} + \sum_{j=0}^{8} x_{i,j}\right) \equiv 0 \pmod{2}, ] [ \text{For each column } j: \quad \left(\sum_{i=0}^{8} a_{i,j} + \sum_{i=0}^{8} x_{i,j}\right) \equiv 0 \pmod{2}, ] [ \text{For each subgrid } s: \quad \left(\sum_{(i,j) \in s} a_{i,j} + \sum_{(i,j) \in s} x_{i,j}\right) \equiv 0 \pmod{2}. ]

Your task is to determine the minimum number of toggles required to satisfy the parity conditions for all rows, columns, and subgrids.

Input Example:

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

Output Example:

3

inputFormat

The input consists of 9 lines. Each line contains a string of 9 characters, each either '0' or '1', representing a row of the binary Sudoku board.

outputFormat

Output a single integer — the minimum number of toggles required so that every row, every column, and every 3×3 subgrid has an even number of ones.

sample

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

3