탈옥

상근이는 감옥에 갇힌 죄수 두 명을 탈옥시켜야 한다. 감옥은 1층짜리 건물이고, 상근이는 방금 그 평면도를 손에 넣었다.

평면도에는 벽과 문이 모두 나와 있고, 탈옥시켜야 하는 죄수 두 명의 위치도 나와 있다. 무인 감옥이라 이 두 명 말고 다른 사람은 없다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술로 제어실을 거치지 않고 문을 열려고 하는데, 문 하나를 여는 데 시간이 아주 오래 걸린다. 한 번 연 문은 계속 열린 채로 남는다. 죄수 두 명을 모두 감옥 밖으로 내보내려면 문을 최소 몇 개 열어야 하는지 구하는 프로그램을 작성하시오.

사람은 상하좌우로 붙어 있는 칸으로만 움직이고, 벽이 있는 칸은 지나갈 수 없다. 평면도 바깥은 전부 트인 공간이라 자유롭게 돌아다닌다.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 이어지는 h개 줄에는 평면도가 한 줄에 w글자씩 주어진다. 빈 공간은 ., 지나갈 수 없는 벽은 *, 문은 #, 죄수의 위치는 $이다.

평면도에 표시된 죄수는 항상 두 명이고, 각 죄수에서 감옥 바깥까지 이어지는 경로가 항상 존재하는 입력만 주어진다.

각 테스트 케이스마다 죄수 두 명을 모두 탈옥시키는 데 열어야 하는 문 개수의 최솟값을 한 줄에 하나씩 출력한다.