Граючи в шахи на р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дного потоку м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

Пояснення

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

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