바위, 가위, 보

바트의 여동생 리사가 2차원 격자 위에 새로운 문명을 만들었다. 처음에 각 칸은 세 가지 생명체 중 하나로 채워져 있을 수 있는데, 바로 바위(Rock), 가위(Scissors), 보(Paper)이다. 매일, 가로 또는 세로로 인접한 두 칸에 서로 다른 생명체가 있으면 그 사이에서 전쟁이 벌어진다. 모든 전쟁에서 바위는 항상 가위를 이기고, 가위는 항상 보를 이기며, 보는 항상 바위를 이긴다. 하루가 끝나면 승자는 패자의 칸까지 영역을 넓혀 그 칸을 차지하고, 패자는 그 칸에서 사라진다. 같은 날에 일어나는 모든 전쟁은 동시에 처리된다.

$n$일이 지난 뒤 각 생명체가 차지하고 있는 영역을 구하여라.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다. 각 테스트 케이스의 첫째 줄에는 세 정수 $r$, $c$, $n$이 주어지며, 각각 격자의 행 수, 열 수, 그리고 지나가는 날 수를 뜻한다. 세 정수는 모두 100 이하이다. 이어지는 $r$개의 줄에는 각각 $c$개의 문자로 격자가 주어진다. 각 문자는 R, S, P 중 하나이며, 각각 그 칸이 바위(Rock), 가위(Scissors), 보(Paper)로 채워져 있음을 나타낸다.

각 테스트 케이스에 대해 $n$일이 끝난 뒤의 격자를 출력한다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣는다.