Миссия Джона состоит в том, чтобы вытащить двух человек из тюрьмы. Тюрьма представляет собой одноэтажное здание. Джон сумел достать подробный план этажа с указанием всех стен и дверей. Он также знает расположение двух людей, которых должен освободить. Тюремные охранники не проблема - он спланировал диверсию, в результате которой они покинут здание практически незаметно.

Двери являются его главной проблемой. Все двери, как правило, удаленно открываются из диспетчерской, однако Джон может открыть их с помощью других средств. После того как ему удалось открыть дверь, она остается открытой. Тем не менее открытие двери занимает много времени. Поэтому он хочет свести к минимуму количество дверей, которое он должен открыть. Сможете ли Вы помочь Джону спланировать оптимальный маршрут, по которому он сможет добраться до двух заключенных?

Входные данные

Первая строка содержит количество тестов, не более 100. Каждый тест содержит:

• одна строка содержит два числа h и w (2 ≤ h, w ≤ 100): ширину и высоту карты.
• h строк по w символов описывающих здание тюрьмы:
• '.' пустое место.
• '*' непроницаемая стена.
• '#' дверь.
• '$' один из двух людей которых следует освободить.

Джон может свободно перемещаться по внешней стороне здания. Карта содержит ровно два человека. До каждого человека внутри тюрьмы существует путь из внешней стороны.

Выходные данные

Для каждого теста вывести в отдельной строке наименьшее количество дверей, которое Джон должен открыть для освобождения обоих узников.