Cho gà ăn

Một nông trại được mô tả bằng lưới chữ nhật gồm $r$ hàng và $c$ cột. Mỗi ô của lưới hoặc chứa thóc (ký hiệu bằng chữ R) hoặc để trống (ký hiệu bằng dấu .).

Trên nông trại có $k$ con gà. Bạn cần chia toàn bộ các ô của lưới cho $k$ con gà sao cho:

• Mỗi ô được giao cho đúng một con gà.
• Mỗi con gà được giao ít nhất một ô.
• Tập các ô của mỗi con gà tạo thành một vùng liên thông: từ một ô bất kỳ của con gà đó có thể đi tới mọi ô khác của nó bằng cách di chuyển giữa hai ô kề cạnh và chỉ đi qua các ô thuộc chính con gà đó.

Để đàn gà không tranh giành thức ăn, hãy chia sao cho hiệu giữa số ô thóc nhiều nhất và số ô thóc ít nhất mà một con gà nhận được là nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên $T$: số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

• Dòng đầu chứa ba số nguyên $r$, $c$, $k$.
• $r$ dòng tiếp theo, mỗi dòng chứa $c$ ký tự . hoặc R, mô tả lưới.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra $r$ dòng, mỗi dòng gồm $c$ ký tự. Mỗi ký tự phải là chữ cái thường, chữ cái hoa hoặc chữ số. Hai ký tự bằng nhau khi và chỉ khi hai ô tương ứng được giao cho cùng một con gà. Chữ hoa và chữ thường được coi là khác nhau, nên A và a là hai con gà khác nhau.

Nếu có nhiều cách chia tối ưu, in ra cách bất kỳ.

Ràng buộc

• $1\le T\le 2·{10}^4$
• $1\le r,c\le 100$
• $1\le k\le 62$
• Số con gà không vượt quá số ô chứa thóc của lưới.
• Tổng $r·c$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^4$.

Ví dụ