\includegraphics{https://static.e-olymp.com/content/f7/f710295a2c525422b5d6a1b2fbb371a356d550fc.jpg} Олімпіада -- спортивна подія світового масштабу. Місто, якому пощастило приймати у себе Олімпійські ігри, кожен раз намагається вразити мільйони вболівальників, які приїхали підтримати свої команди, а також спортсменів і усіх, для кого великі Ігри стерли кордони країн та континентів. У Лондона великий досвід в частині проведення Олімпіади: столиця Великобританії приймала у 2012 році Ігри у рекордний третій раз. У попередні два, в 1908 та 1948 роках, з об'єктивних причин не вдалось влаштувати грандіозного святкування, тому на цей раз було вирішено святкувати з розмахом. До створення олімпійських об'єктів, проте, англійці підійшли по-британському раціонально, застосувавши стратегію бережливого будівництва. При споруджені арен використовувались сучасні матеріали, які дозволяли після проведення змагань швидко і легко демонтувати об'єкти. Для багаточислених відвідувачів були спеціально виготовлені спеціальні карти з олимпійськими (і не лише) видатними місцями Лондона. Ось і Васі потрапила до рук одна з таких карт. У нього саме виявилась невелика кількість вільного часу від цікавих для нього змагань, і він хоче влаштувати собі туристичену прогулянку, при цьому відвідавши якомога більше цікавих об'єктів, відмічених на карті. Правила вуличного руху у Лондоні досить своєрідні, проте Вася вирішил їх особливо не вчити -- він на практиці перевірив, що якщо він рухається по дорозі зі свого готеля, розміщеного у північно-західній частині міста лише на південь чи на схід, а назад повертається, рухаючись лише на захід чи північ, то проблем у нього ніколи не виникає. Ваша задача полягає у складанні такого маршруту для Васі, щоб він, рухаючись за своїми правилами, відвідав якомога більше видатних місць олімпійського Лондону і при цьому повернувся назад в готель. \InputFile У першому рядку вхідного файлу задано кількість тестових випадків (не більше \textbf{20}). Кожен тестовий випадок у першому своєму рядку містить два числа: \textbf{W} та \textbf{H} (\textbf{2} ≤ \textbf{W}, \textbf{H} ≤ \textbf{100}), ширину та висоту карти. Наступні \textbf{H} рядків кожного тестового випадку містять по \textbf{W} символів кожен і позначають: \begin{itemize} \item '\textbf{.}' - вільну область, по якій можна переміщуватись; \item '\textbf{*}' - цікавий об'єкт (він також є областю, доступною для переміщення); \item '\textbf{#}' - заблоковані області (ці області не доступні для переміщення по ним). \end{itemize} Можете вважати, что від готеля, де проживає Вася, який знаходиться у лівому верхньому куті карти, до правого нижнього кута карти завжди існує дорога. \OutputFile Для кожного тестового випадку в окремому рядку виведіть єдине число -- найбільшу кількість цікавих об'єктів, які зможе відвідати Вася. Один і той же цікавий олімпійський чи туристичний об'єкт, відвіданий двічі, враховується лише один раз.