Harvesting a Farm

A farmer owns a rectangular farm. The farm is divided into $n \times m$ equal-sized square cells, and each cell has one of two crops planted in it: wheat or corn. Wheat is denoted by the digit 1 and corn by the digit 2.

Through many years of experience, the farmer has found that, to improve crop quality, no adjacent $2 \times 2$ block of cells may form either of the following two "crossing" patterns. (Every farm given in the input always satisfies this rule.)

Crossing pattern 1

Crossing pattern 2

The farmer has a combine for harvesting. To harvest a given crop, a special cutter matching that crop must be attached to the combine. While no cutter is attached, and also while a cutter is being replaced, the combine may be moved freely to any cell of the farm without harvesting anything. However, once a cutter is attached, the combine may move only over cells planted with the crop matching that cutter, or over cells that are already empty (harvested earlier).

Because replacing a cutter is tedious, the farmer wants to minimize the number of cutter replacements needed to harvest the entire farm. Write a program that computes this minimum number of cutter replacements.

The input consists of multiple test cases. The first line of each test case contains two integers $n$ and $m$, the number of rows and columns of the farm ($1 \le n \times m \le 10^5$). Each of the next $n$ lines contains $m$ characters from the set $\{1, 2\}$, giving the crop planted in the corresponding cell. The input ends with a line containing 0 0.

For each test case, print on its own line the minimum number of times the farmer must replace the combine's cutter. Attaching a cutter to the combine for the first time also counts as one replacement.