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