\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 Для каждого тестового случая в отдельной строке выведите единственное число -- наибольшее количество интересных объектов, которые сможет посетить Вася. Один и тот же интересный олимпийский или туристический объект, посещённый дважды, учитывается только один раз.