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