Граючи в шахи на рiзних турнiрах, Марта декiлька разiв програла партiю пiд час турових ендшпiлiв. На тренуваннях, про розглядi рiзних турових розкладок, у неї виникла iдея такої задачi.

На шаховiй дошцi розмiрнiстю \(N\) x \(M\) Марта розмiстила \(K\) королiв. Тепер треба розмiстити мiнiмальну кiлькiсть тур так, щоб виконувалися наступнi умови:

• жоден король не знаходиться пiд боєм тури;

• кожен король iзольований, тобто вiн не може дiйти до iншого короля, щоб не перетнути поле пiд боєм тури або взявши туру.

Допоможiть Мартi перевiрити свої розв’язки: напишiть програму, яка визначить необхiдну мiнiмальну кiлькiсть тур. Обмеження:

\(1 \le N, M \le 1024\)

\(N · M \le 1024\)

Пояснення

Наприклад, туру можна розмiстити так:

........
........
..K.....
......K.
........
...T....
.K..K...
........

Формат вхідних даних

Перший рядок вхiдного потоку мiстить два цiлих додатних числа \(N\) i \(M\) , роздiлених пропуском.

Наступнi \(N\) рядкiв описують шахову дошку. Кожен iз цих рядкiв мiстить рядок довжиною \(M \), який мiстить символи ’.’ i ’K’, що позначають вiдповiдно порожню клiтину та клiтину iз королем.

Формат вихідних даних

Виведiть мiнiмальну кiлькiсть тур для блокування королiв або -1, якщо це зробити неможливо.

Приклад вхідних даних

8 8
........
........
..K.....
......K.
........
........
.K..K...
........

Приклад вихідних даних

1