Чудовий весняний ранок після дуже важкої ночі продовжується. Завершивши з обрахунками, Вадим збирається прибирати всю свою кімнату. Однак в кота Паштета свої плани - він влаштував полювання за знаряддям для прибирання. Схоже, прибирання затягнеться, а тому Вадимчик вирішив розділити свою кімнату на сектори та прибирати в тих, куди Паштет не може пройти.
Кімната представляє з себе прямокутник розмірами \(N\) на \(M\) клітинок. В одній з клітинок кімнати сидить Паштет, відмічений літерою \(P\). Деякі клітинки забруднені сметаною, вони відмічені літерою \(S\). Порожні клітинки відмічені символом \("."\) (крапка). Стіни та перешкоди відмічені символом - \(#\).
Паштет може пересуватися лише на вільні клітинки, що суміжні з його поточною клітинкою. Кіт не вміє стрибати по діагоналі. Сметана не є перешкодою для кота. Допоможіть Вадиму порахувати, скільки максимально секторів він зможе прибрати у своїй кімнаті не залежно від того, чи є там сметана.
P.S. Усі імена та герої вигадані, а будь-які співпадіння є випадковими.
Програма читає зі стандартного пристрою введення.
У першому рядку 2 цілих число \(N, M\) ( \( 3 < N < 10^3, 3 < M < 10^3 \) ) - розміри кімнати.
У наступних \(N\) рядках знаходиться по \(M\) символів - карта кімнати.
Програма пише у стандартний поток виведення одне число - кількість секторів які Вадим зможе прибрати.
5 6 ###### #.P#S# ####.# #...## ######
2
9 9 ######### #SP.#...# #SS.#.S## ###.#S#.# #.####..# #..##SSS# #####S.S# #...#S.S# #########
4