Farmer John의 소들은 인기 게임 "스도쿠"의 재미있는 변형을 즐깁니다. 일반 스도쿠처럼 $3 \times 3$ 부분 격자로 이루어진 $9 \times 9$ 격자를 사용합니다. 하지만 소들의 스도쿠는 이진 숫자만 사용합니다.

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

이진 스도쿠의 목표는 가능한 한 적은 비트를 뒤집어 아홉 행, 아홉 열, 아홉 개의 $3 \times 3$ 부분 격자 각각이 짝수 패리티 (즉 $1$의 수가 짝수)를 갖도록 하는 것입니다. 위 예에서는 3번의 뒤집기로 올바른 답을 얻을 수 있습니다.

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

이진 스도쿠 판의 초기 상태가 주어집니다. 이를 해결하는 데 필요한 최소 뒤집기 횟수를 구하도록 소들을 도와주세요.

입력

• $1..9$번째 줄: 각 줄에는 초기 판의 한 행에 대응하는 9자리 이진 문자열이 주어집니다.

출력

• 1번째 줄: 모든 행, 열, 부분 격자가 짝수 패리티를 갖게 하는 최소 뒤집기 횟수.

예제

입력 1

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

출력 1

3

참고

예제 입력의 스도쿠 판은 위 문제 설명의 판과 같습니다.

세 번의 뒤집기로 퍼즐을 해결할 수 있습니다.

문제 작성: Brian Dean