Місія Джона полягає в тому, щоб витягти двох людей із в'язниці. В'язниця є одноповерховою будівлею. Джон зумів дістати докладний план поверху із зазначенням усіх стін та дверей. Він також знає розташування двох людей, яких має звільнити. Тюремні охоронці не проблема – він спланував диверсію, внаслідок якої вони покинуть будівлю практично непомітно.

Двері є його головною проблемою. Всі двері, як правило, віддалено відчиняються з диспетчерської, проте Джон може відкрити їх за допомогою інших засобів. Після того як йому вдалося відчинити двері, вони залишаються відчиненими. Проте відкриття дверей займає багато часу. Тому він хоче звести до мінімуму кількість дверей, які він повинен відчинити. Чи зможете Ви допомогти Джону спланувати оптимальний маршрут, яким він зможе дістатися до двох ув'язнених?

Вхідні дані

Перший рядок містить кількість тестів не більше 100. Кожен тест містить:

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

Джон може вільно пересуватися по зовнішній стороні будівлі. Карта містить рівно дві людини. До кожної людини всередині в'язниці існує шлях із зовнішнього боку.

Вихідні дані

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