로맨틱 왕

왕비를 무척 사랑하는 왕이 있었다. 어느 날 왕은 왕비를 기쁘게 해 주려고 깜짝 파티를 준비했지만, 파티가 시작되기 몇 시간 전에 왕비에게 줄 선물을 준비하지 않았다는 사실을 깨달았다.

다행히 왕과 왕비가 사는 도시 주변에는 선물 나무가 자란다. 왕은 가능한 한 많은 선물을 가져가고 싶지만, 평소 운동을 전혀 하지 않아 들고 있는 선물이 많을수록 이동 속도가 느려진다.

왕은 K에서 출발해 주어진 시간 안에 왕비가 있는 성 Q에 도착해야 한다. 왕은 선물을 들고 있지 않으면 한 칸을 이동하는 데 1시간이 걸린다. 선물을 q개 들고 있으면 한 칸을 이동하는 데 q + 1시간이 걸린다. 각 선물 나무 G에서는 선물 하나를 얻을 수 있다. 선물을 더 가지러 가는 동안 왕비가 있는 칸을 지나쳐도 되며, 마지막에 그 칸에 도착하면 된다.

왕이 왕비에게 가져다줄 수 있는 선물의 최대 개수를 구하라.

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 한 줄에 도시 지도의 세로 크기, 가로 크기, 주어진 시간이 주어진다. 이어서 세로 크기개의 줄에 도시 지도가 주어진다.

지도에 사용되는 문자는 다음과 같다.

• Q: 왕비가 있는 성
• K: 왕의 현재 위치
• G: 선물 나무
• .: 길
• #: 지나갈 수 없는 칸

도시 지도의 세로 크기와 가로 크기는 각각 1 이상 50 이하이다. 한 도시에 있는 선물 나무는 0개 이상 16개 이하이다. 입력은 항상 왕이 왕비가 있는 곳에 도착할 수 있는 경우만 주어진다.

각 테스트 케이스마다 왕이 왕비에게 가져다줄 수 있는 선물의 최대 개수를 출력한다.