ADOM

한 로그라이크(roguelike) 게임은 세계를 ASCII 문자로 그립니다. 모든 칸은 정사각형이며, 지도에는 건물의 벽과 주인공이 표시됩니다. 우리는 주인공이 무엇을 볼 수 있는지 계산해야 합니다.

가시성 모형은 현실적입니다. 벽에 가려진 물체는 보이지 않으며, 주인공은 자신의 시야 반경 $r$ 이내에 있는 물체만 인식할 수 있습니다. 이 단순화된 문제에서 지도 위의 물체는 건물의 정사각형 벽뿐입니다.

주어진 지도에서 주인공이 볼 수 있는 벽이 어느 것인지 판별하세요.

첫째 줄에 테스트 케이스의 개수 $T$ $(1 \le T \le 100)$ 가 주어집니다.

각 테스트 케이스의 첫째 줄에는 세 정수 $n$, $m$, $r$ $(1 \le n, m, r \le 100)$ 이 주어지며, 각각 판의 높이, 판의 너비, 주인공의 시야 반경을 뜻합니다.

이어서 $m$ 개의 문자로 이루어진 $n$ 개의 줄로 판이 묘사됩니다. 문자 . 은 빈 칸, X 는 벽, P 는 주인공의 위치를 나타냅니다. 각 판에는 정확히 하나의 P 가 있습니다.

각 테스트 케이스마다, 주인공이 보지 못하는 벽(X)을 모두 . 로 바꾼 판을 출력합니다. $T$ 개의 판을 순서대로 출력하되, 연속한 두 판 사이는 하나의 빈 줄로 구분합니다.

가시성은 다음과 같이 정의합니다.

• 벽 X 는 자신의 정사각형 칸을 빈틈없이 가득 채우며, 이웃한 두 벽 사이에는 어떤 틈도 없습니다.
• 주인공의 관측점은 P 가 있는 칸의 정확한 중심입니다.
• 어떤 벽이 차지하는 정사각형 안의 점 $Q$ 가 존재하여, (1) 관측점에서 $Q$ 까지의 직선 거리가 $r$ 이하이고, (2) 관측점에서 $Q$ 로 가는 열린 선분이 다른 벽의 정사각형 내부를 지나지 않으면, 그 벽은 보이는 것으로 간주합니다. 즉 벽의 가장 작은 조각이라도 보이면 그 벽은 보이는 것입니다.
• 각 벽은 자신의 칸을 완전히 채우고 이웃한 벽 사이에 틈이 없으므로, 두 벽이 오직 한 꼭짓점에서만 맞닿는 지점을 지나는 시선은 통과할 수 없습니다.