색상 통일 게임은 \(3 \times 3\)의 격자로 이루어지고, 각 칸은 흰색 또는 검은색이다.

어떤 칸을 선택하면 그 칸의 색이 반전되며, 그와 동시에 상하좌우의 인접한 칸들 또한 색이 반전된다.

예를 들어 \((1, 2)\)를 선택하면 \((1, 1), (1, 2), (1, 3), (2, 2)\)의 색이 반전된다.

이것을 여러 번 시도하고, 진행 도중에 모든 칸의 색이 동일해지면 게임이 즉시 종료된다.

컴공이는 게임판의 상태를 노드로 생각하여 그래프를 탐색하면 게임을 끝내는 최소 횟수를 알아낼 수 있음을 알게 되었다.

몇 번의 시도 만에 게임이 종료될까?

입력

• 첫 번째 줄부터 세 번째 줄까지 격자의 초기 상태가 주어진다. 0은 흰색이며, 1은 검은색이다.

출력

• 최소 몇 번의 시도에 게임이 종료되는지 출력한다.

입력 예시 1

1 0 0
0 1 1
1 0 0

출력 예시 1

2

입력 예시 2

1 0 0
0 0 0
0 0 0

출력 예시 2

4