Les vaches ont un nouveau système laser pour discuter tranquillement au pâturage, modélisé par une grille de $W \times H$ points ($1 \le W \le 100; 1 \le H \le 100$).

Le système exige une sorte de connexion en ligne de vue pour maintenir la communication. Rochers et arbres la perturbent, mais les vaches ont acheté des miroirs diagonaux (/ et \ ci-dessous) qui dévient le laser de $90$ degrés. La carte suivante illustre le problème.

Sur cette carte, $H=8$ et $W=7$. Les deux vaches qui communiquent sont indiquées par $C$ ; les rochers et autres obstacles par * :

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

Déterminez le nombre minimal de miroirs $M$ à installer pour maintenir la communication laser entre les deux vaches. Cela est toujours possible dans les tests donnés.

Entrée

• Ligne 1 : deux entiers séparés par un espace : $W$ et $H$.
• Lignes $2,\ldots,H+1$ : tout le pâturage.

Sortie

• Ligne 1 : un entier $M$.

Exemples

Entrée 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

Sortie 1

3

Crédits du problème : Rob Kolstad, 2008