Hai người bạn Hòa và An đều có chung sở thích là các số nguyên tố và ma trận. Một lần An ngồi và đem ~ n ~ số nguyên tố đầu tiên sắp xếp thành ma trận vuông, loay hoay một hồi An rất thích thú với tác phẩm của mình, đó là An đã sắp xếp các số nguyên tố này thành ma trận vuông nhưng trên các hàng và các cột của ma trận không có cặp số nào lặp lại. An đem tác phẩm của mình đi khoe Hòa nhưng muốn thử bạn, An đã xóa một số số trên ma trận và đố Hòa điền các số đã bị xóa sao cho thu được ma trận vuông giống tác phẩm của mình.

Yêu cầu: Hãy giúp bạn Hòa thực hiện câu đố của An.

Dữ liệu vào

• Dòng đầu là số nguyên dương ~ n ~ ~ ( 2 ≤ n ≤ 15 ) ~
• ~ n ~ dòng sau là thông tin về ma trận đã mất một số số, ô bị mất sẽ có giá trị là 0

Kết quả

• Ghi ~ n ~ dòng là ma trận sau khi đã điền vào các số bị mất.

Nếu có nhiều kết quả thì in ra kết quả có các số điền vào theo thứ tự từ trên xuống dưới, từ trái qua phải là nhỏ nhất

Ví dụ:

Input 1

4
3 0 7 2
0 7 3 0
5 0  0 7
0 2 0 3 

Output 1

3 5 7 2
2 7 3 5
5 3 2 7
7 2 5 3