미로

한 모험가가 입구에서 출구까지 이어진 미로를 지나가려 한다. 미로의 구조를 모르기 때문에 길이 갈라지는 곳에서는 아직 들어가 보지 않은 길 중 하나를 같은 확률로 고른다. 한 번 조사한 길을 다시 새 길처럼 선택하지 않으며, 더 이상 새 길이 없다고 판단했을 때만 왔던 길을 되돌아간다.

미로에는 같은 지점으로 돌아오는 사이클이 없고, 열린 칸이 2×2 이상으로 붙어 있는 공간도 없다. 입구와 출구는 각각 하나이며 모두 미로의 경계에 있다. 출구가 길 바로 옆에 있더라도, 그 방향도 갈림길의 한 선택지로 본다.

모험가가 입구에서 출구까지 도달하기까지 걷는 칸 이동 횟수의 기댓값을 구하라.

첫 줄에 테스트 케이스의 개수 n (0 < n ≤ 100)이 주어진다.

각 테스트 케이스는 다음 형식으로 주어진다.

• 첫 줄에 미로의 높이 h와 너비 w (3 ≤ h, w ≤ 96)가 주어진다.
• 이어서 h개의 줄에 길이가 w인 문자열이 주어진다.
  • #은 벽이다.
  • s는 입구, t는 출구다.
  • .은 이동할 수 있는 길이다.
• 입구와 출구를 제외한 미로의 경계는 모두 벽이다.
• 입구와 출구는 항상 경계에 있다.

각 테스트 케이스마다 한 줄에, 입구에서 출구까지 도달하는 데 필요한 걸음 수의 기댓값을 반올림하여 소수 둘째 자리까지 출력한다.