L'administration de la ville de Zagreb a décidé de construire un nouveau parking. Pour ce faire, elle utilisera un terrain de forme rectangulaire que l'on peut imaginer comme une matrice de $N$ lignes et $M$ colonnes. Afin d'attirer les visiteurs et d'augmenter ainsi les revenus, le maire a décidé d'installer des fontaines, des puits et d'autres types de jets d'eau sur des emplacements prédéterminés du terrain. Les cases restantes sont prévues pour la circulation des véhicules et seront réaménagées selon l'une des deux possibilités suivantes : places de parking, ou zones de circulation libre pour les véhicules.

Les véhicules peuvent se déplacer sur le parking en se déplaçant à chaque étape vers une case adjacente dans l'une des quatre directions (nord, sud, est ou ouest). Le parking doit être conçu de telle sorte qu'à tout moment, depuis chaque place de parking, il soit possible d'atteindre l'entrée/sortie du parking située dans la case en haut à gauche (à l'intersection de la première ligne et de la première colonne), c'est-à-dire que les véhicules stationnés sur les places de parking ne doivent pas bloquer la sortie aux autres véhicules. En d'autres termes, chaque véhicule garé doit être en mesure de quitter le parking sans déplacer d'autres véhicules garés.

Aidez le maire à déterminer le nombre maximal possible de places de parking pour le terrain donné.

Remarque : La case située à la première ligne et à la première colonne est l'entrée du parking ; elle n'est pas destinée au stationnement et sera toujours libre.

Entrée

La première ligne contient les entiers naturels $N$ et $M$ ($1 \le N \le 6$, $1 \le M \le 100$), le nombre de lignes et de colonnes du terrain. Les $N$ lignes suivantes contiennent chacune $M$ caractères décrivant l'aspect du terrain : le caractère 'x' désigne une case où une fontaine sera construite, les autres cases sont marquées par le caractère '.' et seront réaménagées pour le parking.

Sortie

Sur une seule ligne, affichez le nombre maximal possible de places de parking.

Exemples

Entrée 1

3 3
...
.x.
...

Sortie 1

2

Entrée 2

3 3
...
..x
...

Sortie 2

4

Entrée 3

3 6
.x..x.
..x.x.
......

Sortie 3

3

Entrée 4

4 5
....x
....x
..x..
.x..x

Sortie 4

7

Remarque

Explication du quatrième exemple : un agencement possible des places de parking :

.PPPx
....x
.Px.P
PxP.x