Туристична прогулянка
Олімпіада – спортивна подія світового масштабу. Місто, якому пощастило приймати у себе Олімпійські ігри, кожен раз намагається вразити мільйони вболівальників, які приїхали підтримати свої команди, а також спортсменів і усіх, для кого великі Ігри стерли кордони країн та континентів.
У Лондона великий досвід в частині проведення Олімпіади: столиця Великобританії приймала у 2012 році Ігри у рекордний третій раз. У попередні два, в 1908 та 1948 роках, з об'єктивних причин не вдалось влаштувати грандіозного святкування, тому на цей раз було вирішено святкувати з розмахом.
До створення олімпійських об'єктів, проте, англійці підійшли по-британському раціонально, застосувавши стратегію бережливого будівництва. При споруджені арен використовувались сучасні матеріали, які дозволяли після проведення змагань швидко і легко демонтувати об'єкти.
Для багаточислених відвідувачів були спеціально виготовлені спеціальні карти з олимпійськими (і не лише) видатними місцями Лондона. Ось і Васі потрапила до рук одна з таких карт. У нього саме виявилась невелика кількість вільного часу від цікавих для нього змагань, і він хоче влаштувати собі туристичену прогулянку, при цьому відвідавши якомога більше цікавих об'єктів, відмічених на карті.
Правила вуличного руху у Лондоні досить своєрідні, проте Вася вирішил їх особливо не вчити – він на практиці перевірив, що якщо він рухається по дорозі зі свого готеля, розміщеного у північно-західній частині міста лише на південь чи на схід, а назад повертається, рухаючись лише на захід чи північ, то проблем у нього ніколи не виникає.
Ваша задача полягає у складанні такого маршруту для Васі, щоб він, рухаючись за своїми правилами, відвідав якомога більше видатних місць олімпійського Лондону і при цьому повернувся назад в готель.
Вхідні дані
У першому рядку вхідного файлу задано кількість тестових випадків (не більше 20). Кожен тестовий випадок у першому своєму рядку містить два числа: W та H (2 ≤ W, H ≤ 100), ширину та висоту карти. Наступні H рядків кожного тестового випадку містять по W символів кожен і позначають:
'.' - вільну область, по якій можна переміщуватись;
'*' - цікавий об'єкт (він також є областю, доступною для переміщення);
'#' - заблоковані області (ці області не доступні для переміщення по ним).
Можете вважати, что від готеля, де проживає Вася, який знаходиться у лівому верхньому куті карти, до правого нижнього кута карти завжди існує дорога.
Вихідні дані
Для кожного тестового випадку в окремому рядку виведіть єдине число – найбільшу кількість цікавих об'єктів, які зможе відвідати Вася. Один і той же цікавий олімпійський чи туристичний об'єкт, відвіданий двічі, враховується лише один раз.