Các con bò của Farmer John thích chơi một biến thể thú vị của trò chơi «Sudoku» phổ biến. Phiên bản của chúng dùng lưới $9 \times 9$ gồm các lưới con $3 \times 3$, giống sudoku thông thường. Tuy nhiên, phiên bản của bò chỉ dùng các chữ số nhị phân:

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

Mục tiêu của sudoku nhị phân là đảo ít bit nhất có thể để mỗi hàng trong chín hàng, mỗi cột trong chín cột và mỗi lưới con trong chín lưới con $3 \times 3$ có tính chẵn (tức là chứa số lượng chữ số $1$ chẵn). Với ví dụ trên, một tập hợp 3 lần đảo cho một lời giải hợp lệ:

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

Cho trạng thái ban đầu của bảng sudoku nhị phân, hãy giúp các con bò xác định số lần đảo ít nhất cần thiết để giải nó.

Dữ liệu vào

• Các dòng $1..9$: mỗi dòng chứa một chuỗi nhị phân 9 chữ số tương ứng với một hàng của bảng ban đầu.

Dữ liệu ra

• Dòng 1: số lần đảo ít nhất để mọi hàng, cột và lưới con đều có tính chẵn.

Ví dụ

Dữ liệu vào 1

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

Dữ liệu ra 1

3

Ghi chú

Bảng sudoku trong dữ liệu vào mẫu giống bảng trong phần mô tả bài toán ở trên.

Ba lần đảo là đủ để giải câu đố.

Tác giả bài toán: Brian Dean