Problem description

Dwaj gracze grają w grę na prostokątnej planszy o wymiarach N × M. Plansza składa się z pól, które początkowo mogę być puste albo zajęte. Gracze na zmianę kładą kamienie na pustym polu, zajmując je. Każdy kolejny kamień musi być sąsiadem poprzedniego (muszą mieć wspólny bok), z wyjątkiem pierwszego, który można położyć w dowolnym pustym miejscu. Gra kończy się, gdy gracz nie może wykonać ruchu – wtedy przegrywa, a drugi gracz wygrywa.

Twoim zadaniem jest policzyć, ile pól jest wygrywających – czyli takich, że jeśli pierwszy gracz postawi tam pierwszy kamień, to wygra grę przy optymalnej grze obu stron.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i M, będące wymiarami planszy. W kolejnych N wierszach znajduje się opis planszy, w każdym z nich znajduje się ciąg M symboli – kropka (.) odpowiada polu pustemu, a kratka (#) polu zajętemu.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita będąca liczbą pól wygrywających.

Ograniczenia

1 ≤ N, M ≤ 50.

Przykład

3 4
.#..
.#.#
....

3

1 5
#...#

2

4 4
..##
..##
##..
##..

0