Bessie kaute zarte Grassprossen und dachte, wie Kühe es tun, über das Universum nach. Sie mag nur das Gras auf weiten Weiden auf der Grundhöhe der Farm. Bereits 1 Meter höher ist es zäher und weniger appetitlich; mit zunehmender Höhe wird es schlechter.

Beim Weiterkauen erkennt sie, dass dieses Gras an Hügelhängen wächst und „Inseln“ in einem Meer aus zartem, grünem, köstlichem und reichlichem Gras bildet.

Bessie zieht einen Laborkittel an und will die Inseln zählen. Sie zeichnet eine Karte mit $R$ Reihen ($1 \lt R \le 1,000$) und $C$ Spalten ($1 \lt C \le 1,000$) aus $1 \times 1$ Meter großen Quadraten. Sie misst die Höhe über dem Grundniveau und rundet sie auf eine nichtnegative ganze Zahl. Hungrig bemerkt sie, dass leckeres Gras immer Höhe 0 hat.

Sie beginnt zu zählen. Zwei horizontal, vertikal oder diagonal benachbarte Quadrate gehören zur selben Insel.

Wie viele Inseln schlechten Grases zählt sie für jede gegebene Karte?

Eingabe

• Zeile $1$: zwei durch ein Leerzeichen getrennte ganze Zahlen: $R$ und $C$.

• Zeilen $2,\ldots,R+1$: Zeile $i+1$ beschreibt Reihe $i$ mit $C$ durch Leerzeichen getrennten ganzen Zahlen.

Ausgabe

• Zeile $1$: eine ganze Zahl, die Anzahl der Inseln.

Beispiele

Eingabe 1

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Ausgabe 1

2

Hinweis

Es gibt zwei Inseln: Die große links erstreckt sich über eine diagonale Verbindung bis ganz nach unten, die kleine liegt oben rechts.

Aufgabenautor: Fatih, 2008