바다표범 세이모어

바다표범 세이모어는 몹시 속상하다. 평화롭게 맛있는 청어를 먹던 중 커다란 폭발을 목격했을 뿐 아니라(사실 수염 몇 가닥이 살짝 그을리기까지 했다), 이제는 눈을 따갑게 하고 숨쉬기 힘들게 만드는 시커먼 기름 찌꺼기까지 견뎌야 한다. 예전에는 헤엄치는 것이 훨씬 즐거웠다. 세이모어는 이 기름 찌꺼기를 너무 많이 통과하면 몸에 해롭다는 것을 이미 알아냈고, 몇 번은 죽을 뻔하기도 했다. 다행히 해변에는 그를 깨끗이 씻어 주는 친절한 사람들이 있어서, 좋아하는 청어 사냥터까지 무사히 도착하려면 이들을 충분히 자주 찾아가야 한다. 그런데 일부 청어는 이제 너무 많은 기름에 가로막혀 전혀 갈 수 없게 된 듯하다. 그래서 세이모어는 아직 다다를 수 있는 청어 보급지가 몇 곳인지 계산하고 싶어 한다.

세이모어가 사는 동네를 나타내는 2차원 지도가 주어진다. 세이모어는 한 번에 한 칸씩 상하좌우로만 이동할 수 있고, 대각선으로는 이동할 수 없다. 각 문자는 해당 위치에 무엇이 있는지를 나타낸다.

• S: 세이모어의 바다표범 서식지(지도에 정확히 하나 있다). 세이모어는 여기에서 출발한다.
• H: 청어 보급지.
• G: 시커먼 기름.
• P: 친절한 세척원이 있는 장소.
• .: 열린 바다.

세이모어는 기름 칸을 최대 3칸까지만 겨우 헤엄쳐 지날 수 있고, 4번째 기름 칸에 들어가면 죽는다. 세척원을 방문하면 몸이 완전히 깨끗해져서 다시 기름을 3칸 지날 수 있으며, 이 과정을 원하는 만큼 반복할 수 있다. 열린 바다나 청어 칸을 지나는 것은 누적된 기름을 초기화하지 않으며, 오직 세척원 방문만이 초기화한다.

출발지 S에서 시작하여, 도중에 죽지 않고 다다를 수 있는 청어 보급지 H의 개수를 구하여라.

첫 번째 줄에 데이터 세트의 개수 $K$가 주어진다. 그 뒤로 $K$개의 데이터 세트가 이어지며, 각 데이터 세트는 다음과 같은 형식이다.

첫 번째 줄에는 지도의 크기를 나타내는 두 정수 $x$와 $y$가 주어진다 ($1 \le x, y \le 50$). $x$는 가로 크기(열의 수), $y$는 세로 크기(행의 수)이다.

그다음 $y$개의 줄에 각각 $x$개의 문자가 주어지며, 위에서 설명한 대로 세이모어의 지도 한 행을 나타낸다.

각 데이터 세트에 대해, 먼저 한 줄에 Data Set x:를 출력한다. 여기서 $x$는 데이터 세트의 번호이다. 그다음 줄에 세이모어가 도중에 죽지 않고 다다를 수 있는 청어 보급지의 총 개수를 출력한다. 연속한 두 데이터 세트 사이는 빈 줄 하나로 구분한다.