Trong bài toán này, bạn phải vẽ một hình vuông bằng cách sử dụng bảng chữ cái tiếng Anh viết hoa.

Để chính xác hơn, bạn sẽ được cung cấp một hình vuông với một số khối trống và các khối khác đã được điền sẵn cho bạn với một số chữ cái để làm cho công việc của bạn dễ dàng hơn. Bạn phải chèn ký tự vào mọi ô trống để toàn bộ lưới được lấp đầy bằng bảng chữ cái. Khi làm như vậy bạn phải đáp ứng các quy tắc sau:

1. Đảm bảo không có ô liền kề nào chứa cùng một chữ cái; hai ô liền kề nếu chúng có chung cạnh.
2. Có thể có nhiều cách để lấp đầy lưới điện. Bạn phải đảm bảo bạn điền vào bảng sao cho các chữ cái có thứ tự từ điển nhỏ nhất. Ở đây, hai lưới được kiểm tra theo thứ tự hàng khi so sánh theo từ điển.

INPUT: ALPHABET.INP

• Dòng đầu tiên chứa số nguyên dương T, số lượng bộ test
• Mỗi bộ test có dạng:
  • Dòng đầu chứa số nguyên dương n (n ≤ 20), kích thước của bảng hình vuông.
  • n dòng tiếp theo, mỗi dòng chứa n ký tự ‘.’ (thể hiện ô trống) hoặc ký tự nào đó thuộc đoạn [‘A’, ‘Z’] (thể hiện ô đã được điền sẵn).

OUTPUT: ALPHABET.OUT

• Tương ứng mỗi test, tại test thứ i ghi ra từ “Case i:’
• Các dòng tiếp theo ghi ra bảng chữ cái thoản mãn yêu cầu đề bài