농장 수확하기

농부는 직사각형 모양의 농장을 가지고 있다. 농장은 $n \times m$개의 크기가 같은 정사각형 칸으로 나뉘어 있으며, 각 칸에는 밀 또는 옥수수 중 한 가지 작물이 심어져 있다. 밀은 숫자 1, 옥수수는 숫자 2로 나타낸다.

여러 해에 걸친 경험을 통해, 농부는 작물의 품질을 높이려면 인접한 $2 \times 2$ 칸이 다음 두 가지 "교차" 패턴 중 어느 것도 이루어서는 안 된다는 규칙을 알아냈다. (입력으로 주어지는 농장은 항상 이 규칙을 만족한다.)

교차 패턴 1

교차 패턴 2

농부는 작물을 수확하기 위한 콤바인을 한 대 가지고 있다. 어떤 작물을 수확하려면 그 작물에 맞는 전용 절단기를 콤바인에 장착해야 한다. 절단기가 장착되어 있지 않을 때, 그리고 절단기를 교체하는 동안에는 콤바인을 농장의 어느 칸으로든 자유롭게 옮길 수 있으며 이때는 아무것도 수확하지 않는다. 그러나 일단 절단기가 장착되면, 콤바인은 그 절단기에 맞는 작물이 심어진 칸이나, 이미 수확이 끝나 아무것도 없는 칸 위로만 이동할 수 있다.

절단기를 교체하는 일은 번거롭기 때문에, 농부는 농장 전체를 수확하는 데 필요한 절단기 교체 횟수를 최소로 하고 싶어 한다. 농장 전체를 수확하기 위해 필요한 최소 절단기 교체 횟수를 구하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 농장의 행과 열의 개수를 나타내는 두 정수 $n$과 $m$이 주어진다 ($1 \le n \times m \le 10^5$). 이어지는 $n$개의 줄에는 각각 $m$개의 문자가 주어지며, 각 문자는 집합 ${1, 2}$의 값으로 해당 칸에 심어진 작물의 종류를 나타낸다. 입력은 0 0으로 이루어진 줄로 끝난다.

각 테스트 케이스마다, 농부가 콤바인의 절단기를 교체해야 하는 최소 횟수를 한 줄에 하나씩 출력한다. 콤바인에 절단기를 처음 장착하는 것도 한 번의 교체로 센다.