시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB113922718722.749%

문제

바다에서 수학을 좋아하기로 유명한 오징어의 취미는 스도쿠이다. 스도쿠는 9*9칸으로 이루어져 있으며, 3*3칸에 1~9까지가 1번씩, 각각의 가로줄에도 1번씩, 세로줄에도 1번씩 들어가게 만드는 게임이다.

오징어는 하루를 스도쿠와 함께 시작한다. 스도쿠를 푸는 오징어가 멋있어 보였던 새우는 오징어에게 문제지를 하나만 달라고 요청하였고, 오징어는 문제지를 복사해 주었다.

새우는 오징어보다 스도쿠를 먼저 풀어서 자랑하기 위해 프로그래밍으로 스도쿠를 풀어보려고 한다.

위의 모습 처럼 생긴 스도쿠가 있다면, 숫자는 숫자로, 빈 칸은 0으로 주어진다.

스도쿠를 입력받아 스도쿠를 푸는 프로그램을 작성하시오

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 9개의 줄로 이루어진 스도쿠이다. 또, 각 줄은 0부터 9까지 숫자로 이루어져 있다. 각 테스트 케이스에는 항상 0이 5개가 주어진다.

출력

규칙을 지키면서 스도쿠를 풀 수 없는 경우에는 

Could not complete this grid.

를 출력한다.

스도쿠를 풀 수 있는 경우에는 입력 형식대로 스도쿠를 9개 줄에 걸쳐서 출력한다.

각 테스트케이스 사이에는 빈 줄을 출력하며, 스도쿠를 풀 수 있는 경우에는 항상 정답이 유일한 것만 입력으로 주어진다.

예제 입력 1

2
481253697
267948105
539671204
654389712
908704563
173562849
702136958
315897426
896425371
481253697
267948105
539671284
654289710
908704562
173562849
702136958
315897426
896425371

예제 출력 1

481253697
267948135
539671284
654389712
928714563
173562849
742136958
315897426
896425371

Could not complete this grid.
W3sicHJvYmxlbV9pZCI6IjQwNTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTQtXHVjMmE0LVx1YzJhNFx1YjNjNFx1Y2ZlMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViYzE0XHViMmU0XHVjNWQwXHVjMTFjIFx1YzIxOFx1ZDU1OVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWFlMzBcdWI4NWMgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzYyNFx1YzlkNVx1YzViNFx1Yzc1OCBcdWNkZThcdWJiZjhcdWIyOTQgXHVjMmE0XHViM2M0XHVjZmUwXHVjNzc0XHViMmU0LiBcdWMyYTRcdWIzYzRcdWNmZTBcdWIyOTQgOSo5XHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIDMqM1x1Y2U3OFx1YzVkMCAxfjlcdWFlNGNcdWM5YzBcdWFjMDAgMVx1YmM4OFx1YzUyOSwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWMwMFx1Yjg1Y1x1YzkwNFx1YzVkMFx1YjNjNCAxXHViYzg4XHVjNTI5LCBcdWMxMzhcdWI4NWNcdWM5MDRcdWM1ZDBcdWIzYzQgMVx1YmM4OFx1YzUyOSBcdWI0ZTRcdWM1YjRcdWFjMDBcdWFjOGMgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHVjOWQ1XHVjNWI0XHViMjk0IFx1ZDU1OFx1YjhlOFx1Yjk3YyBcdWMyYTRcdWIzYzRcdWNmZTBcdWM2NDAgXHVkNTY4XHVhZWQ4IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ3OFx1YjI5NCBcdWM2MjRcdWM5ZDVcdWM1YjRcdWFjMDAgXHViYTRiXHVjNzg4XHVjNWI0IFx1YmNmNFx1YzYwMFx1YjM1OCBcdWMwYzhcdWM2YjBcdWIyOTQgXHVjNjI0XHVjOWQ1XHVjNWI0XHVjNWQwXHVhYzhjIFx1YmIzOFx1YzgxY1x1YzljMFx1Yjk3YyBcdWQ1NThcdWIwOThcdWI5Y2MgXHViMmVjXHViNzdjXHVhY2UwIFx1YzY5NFx1Y2NhZFx1ZDU1OFx1YzYwMFx1YWNlMCwgXHVjNjI0XHVjOWQ1XHVjNWI0XHViMjk0IFx1YmIzOFx1YzgxY1x1YzljMFx1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NzQgXHVjOGZjXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzhcdWM2YjBcdWIyOTQgXHVjNjI0XHVjOWQ1XHVjNWI0XHViY2Y0XHViMmU0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWJhM2NcdWM4MDAgXHVkNDgwXHVjNWI0XHVjMTFjIFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkXHVjNzNjXHViODVjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWQ0ODBcdWM1YjRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zdXN1c3Vkb2t1LnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHViYWE4XHVjMmI1IFx1Y2M5OFx1YjdmYyBcdWMwZGRcdWFlMzQgXHVjMmE0XHViM2M0XHVjZmUwXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjg1YywgXHViZTQ4IFx1Y2U3OFx1Yzc0MCAwXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YzU0NCBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDc4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQ8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgOVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWFjMDEgXHVjOTA0XHVjNzQwIDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWIyOTQgXHVkNTZkXHVjMGMxIDBcdWM3NzQgNVx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbkNvdWxkIG5vdCBjb21wbGV0ZSB0aGlzIGdyaWQuPFwvcHJlPlxyXG5cclxuPHA+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3ODVcdWI4MjUgXHVkNjE1XHVjMmRkXHViMzAwXHViODVjIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyA5XHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHVjMmE0XHViM2M0XHVjZmUwXHViOTdjIFx1ZDQ4MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjODE1XHViMmY1XHVjNzc0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjODNcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0MDU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3UtU3UtU3Vkb2t1IiwiZGVzY3JpcHRpb24iOiI8cD5CeSBub3csIGV2ZXJ5b25lIGhhcyBwbGF5ZWQgU3Vkb2t1OiB5b3UmcnNxdW87cmUgZ2l2ZW4gYSA5LWJ5LTkgZ3JpZCBvZiBib3hlcyB3aGljaCB5b3UgYXJlIHRvIGZpbGwgaW4gd2l0aCB0aGUgZGlnaXRzIDEgdGhyb3VnaCA5IHNvIHRoYXQgMSkgZXZlcnkgcm93IGhhcyBhbGwgbmluZSBkaWdpdHMsIDIpIGV2ZXJ5IGNvbHVtbiBoYXMgYWxsIG5pbmUgZGlnaXRzLCBhbmQgMykgYWxsIG5pbmUgMy1ieS0zIHN1YmdyaWRzIGhhdmUgYWxsIG5pbmUgZGlnaXRzLiBUbyBzdGFydCB0aGUgZ2FtZSB5b3UgYXJlIGdpdmVuIGEgcGFydGlhbGx5IGNvbXBsZXRlZCBncmlkIGFuZCBhcmUgYXNrZWQgdG8gZmlsbCBpbiB0aGUgcmVtYWluZGVyIG9mIHRoZSBib3hlcy4gT25lIHN1Y2ggcHV6emxlIGlzIHNob3duIGJlbG93LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zdXN1c3Vkb2t1LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5NHB4OyB3aWR0aDoyMzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIGJlIGdpdmVuIFN1ZG9rdSBncmlkcyB3aGljaCB5b3UgaGF2ZSBuZWFybHkgY29tcGxldGVkOyBpbmRlZWQgeW91JnJzcXVvO3ZlIGZpbGxlZCBpbiBldmVyeSBib3ggZXhjZXB0IGZpdmUuIFlvdSBhcmUgYXNrZWQgdG8gY29tcGxldGUgdGhlIGdyaWQsIG9yIGRldGVybWluZSB0aGF0IGl0JnJzcXVvO3MgaW1wb3NzaWJsZS4gKFlvdSBtaWdodCBoYXZlIGFscmVhZHkgbWFkZSBhbiBlcnJvciEpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCB3aWxsIGNvbnRhaW4gYSBwb3NpdGl2ZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZSBhIG5lYXJseSBjb21wbGV0ZWQgU3Vkb2t1IGdyaWQgY29uc2lzdGluZyBvZiA5IGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgOSBjaGFyYWN0ZXJzIGZyb20gdGhlIHNldCBvZiBkaWdpdHMgMCB0aHJvdWdoIDkuIFRoZXJlIHdpbGwgYmUgZXhhY3RseSBmaXZlIDAmcnNxdW87cyBpbiBlYWNoIHRlc3QgY2FzZSwgaW5kaWNhdGluZyB0aGUgZml2ZSB1bmZpbGxlZCBib3hlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHNob3VsZCBiZSBlaXRoZXI8XC9wPlxyXG5cclxuPHByZT5cclxuQ291bGQgbm90IGNvbXBsZXRlIHRoaXMgZ3JpZC48XC9wcmU+XHJcblxyXG48cD5pZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGNvbXBsZXRlIHRoZSBncmlkIGFjY29yZGluZyB0byB0aGUgcnVsZXMgb2YgdGhlIGdhbWUsIG9yIHRoZSBjb21wbGV0ZWQgZ3JpZCwgaW4gdGhlIGZvcm0gZ2l2ZW4gYmVsb3cuIChUaGVyZSBhcmUgbm8gYmxhbmsgc3BhY2VzIGluIHRoZSBvdXRwdXQuKSBJZiB0aGVyZSBpcyBhIHdheSB0byBjb21wbGV0ZSB0aGUgZ3JpZCwgaXQgd2lsbCBiZSB1bmlxdWUuIFNlcGFyYXRlIHRlc3QgY2FzZXMgd2l0aCBhIGJsYW5rIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > North America > East Central North America Regional > 2008 East Central Regional Contest E번