시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 171 88 80 52.980%

문제

스도쿠는 일본어로 "수독(數獨)"을 읽은 것이다. 이는 미국에서 유명한 일본의 한 퍼즐 이름이기도 하다. 스도쿠는 9x9 격자판에 다음 조건을 만족하여 수를 채워 넣는 게임이다.

  • 각 정수 1-9는 각 행에 정확히 한 번씩 등장해야 한다.
  • 각 정수 1-9는 각 열에 정확히 한 번씩 등장해야 한다.
  • 각 정수 1-9는 각 작은 3x3 정사각형에 정확히 한 번씩 등장해야 한다.

남규는 스도쿠에 푹 빠져서 하루종일 스도쿠 문제를 풀던 와중, 스도쿠를 풀었지만 그것이 정답인지를 쉽게 확인할 수 없어 고민에 빠졌다. 불쌍한 남규를 위해 다 채워진 스도쿠 판이 올바른 답인지 판별하는 프로그램을 작성해 주자.

입력

입력의 첫 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 9개의 줄로 이루어져 있으며, 각 줄에는 9개의 정수가 공백으로 구분되어 있다. 각 정수는 1 이상 9 이하이다. 테스트 케이스의 사이에는 빈 줄이 하나 있다.

테스트 케이스의 개수는 100개를 넘지 않는다.

출력

각 테스트 케이스에 걸쳐 "Case x:"를 출력한 후, 공백 한 칸 뒤에 풀이가 올바르면 "CORRECT"를, 아니면 "INCORRECT"를 출력한다. x는 테스트 케이스 번호이며, 1부터 시작한다.

예제 입력 1

2
1 2 3 5 6 7 4 8 9
3 4 5 6 1 2 4 7 8
7 5 8 3 4 2 1 9 6
1 2 3 5 6 7 4 8 9
3 4 5 6 1 2 4 7 8
7 5 8 3 4 2 1 9 6
1 2 3 5 6 7 4 8 9
3 4 5 6 1 2 4 7 8
7 5 8 3 4 2 1 9 6

3 5 7 9 6 4 2 8 1
4 6 8 1 2 3 5 7 9
9 1 2 5 8 7 4 6 3
6 3 1 7 9 5 8 4 2
7 2 4 3 1 8 6 9 5
8 9 5 2 4 6 1 3 7
1 7 6 4 5 9 3 2 8
5 8 3 6 7 2 9 1 4
2 4 9 8 3 1 7 5 6

예제 출력 1

Case 1: INCORRECT
Case 2: CORRECT
W3sicHJvYmxlbV9pZCI6IjkyOTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWIzYzRcdWNmZTAgXHVjYzQ0XHVjODEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyYTRcdWIzYzRcdWNmZTBcdWIyOTQgXHVjNzdjXHViY2Y4XHVjNWI0XHViODVjICZxdW90O1x1YzIxOFx1YjNjNShcdTY1NzhcdTczNjgpJnF1b3Q7XHVjNzQ0IFx1Yzc3ZFx1Yzc0MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWJiZjhcdWFkNmRcdWM1ZDBcdWMxMWMgXHVjNzIwXHViYTg1XHVkNTVjIFx1Yzc3Y1x1YmNmOFx1Yzc1OCBcdWQ1NWMgXHVkMzdjXHVjOTkwIFx1Yzc3NFx1Yjk4NFx1Yzc3NFx1YWUzMFx1YjNjNCBcdWQ1NThcdWIyZTQuIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1YjI5NCA5eDkgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNWQwIFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHVjNWVjIFx1YzIxOFx1Yjk3YyBcdWNjNDRcdWM2Y2MgXHViMTIzXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFjMDEgXHVjODE1XHVjMjE4IDEtOVx1YjI5NCBcdWFjMDEgXHVkNTg5XHVjNWQwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMSBcdWM4MTVcdWMyMTggMS05XHViMjk0IFx1YWMwMSBcdWM1ZjRcdWM1ZDAgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViNGYxXHVjN2E1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1YzgxNVx1YzIxOCAxLTlcdWIyOTQgXHVhYzAxIFx1Yzc5MVx1Yzc0MCAzeDMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViMGE4XHVhZGRjXHViMjk0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1YzVkMCBcdWQ0NzkgXHViZTYwXHVjODM4XHVjMTFjIFx1ZDU1OFx1YjhlOFx1Yzg4NVx1Yzc3YyBcdWMyYTRcdWIzYzRcdWNmZTAgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YjM1OCBcdWM2NDBcdWM5MTEsIFx1YzJhNFx1YjNjNFx1Y2ZlMFx1Yjk3YyBcdWQ0ODBcdWM1YzhcdWM5YzBcdWI5Y2MgXHVhZGY4XHVhYzgzXHVjNzc0IFx1YzgxNVx1YjJmNVx1Yzc3OFx1YzljMFx1Yjk3YyBcdWMyN2RcdWFjOGMgXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM1YjQgXHVhY2UwXHViYmZjXHVjNWQwIFx1YmU2MFx1Yzg0Y1x1YjJlNC4gXHViZDg4XHVjMzBkXHVkNTVjIFx1YjBhOFx1YWRkY1x1Yjk3YyBcdWM3MDRcdWQ1NzQgXHViMmU0IFx1Y2M0NFx1YzZjY1x1YzljNCBcdWMyYTRcdWIzYzRcdWNmZTAgXHVkMzEwXHVjNzc0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWIyZjVcdWM3NzhcdWM5YzAgXHVkMzEwXHViY2M0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NzQgXHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCA5XHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IDlcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjMjE4XHViMjk0IDEgXHVjNzc0XHVjMGMxIDkgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVjOTA0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDEwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YWM3OFx1Y2NkMCAmcXVvdDtDYXNlIHg6JnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWQ2YzQsIFx1YWNmNVx1YmMzMSBcdWQ1NWMgXHVjZTc4IFx1YjRhNFx1YzVkMCBcdWQ0ODBcdWM3NzRcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc0XHViYTc0ICZxdW90O0NPUlJFQ1QmcXVvdDtcdWI5N2MsIFx1YzU0NFx1YjJjOFx1YmE3NCAmcXVvdDtJTkNPUlJFQ1QmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiB4XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNzc0XHViYTcwLCAxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MjkxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3Vkb2t1IFNvbHV0aW9uIENoZWNrZXIiLCJkZXNjcmlwdGlvbiI6IjxwPlN1ZG9rdSBpcyBhIEphcGFuZXNlIHdvcmQgdGhhdCB0cmFuc2xhdGVzIHRvICZyZHF1bztTaW5nbGUgTnVtYmVyLiZyZHF1bzsgSXQgaXMgYWxzbyB0aGUgbmFtZSBvZiBhIEphcGFuZXNlIGdhbWUgdGhhdCBpcyBwb3B1bGFyIGluIEFtZXJpY2EuIEEgU3Vkb2t1IGJvYXJkIGlzIGEgOXg5IGdyaWQgd2l0aCBudW1iZXJzIGluIGl0LiBJbiBvcmRlciB0byBzb2x2ZSBhIFN1ZG9rdSBQdXp6bGUsIHlvdSBtdXN0IHNhdGlzZnkgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkVhY2ggaW50ZWdlciAxLTkgbXVzdCBhcHBlYXIgaW4gZWFjaCByb3cgZXhhY3RseSBvbmNlPFwvbGk+XHJcblx0PGxpPkVhY2ggaW50ZWdlciAxLTkgbXVzdCBhcHBlYXIgaW4gZWFjaCBjb2x1bW4gZXhhY3RseSBvbmNlPFwvbGk+XHJcblx0PGxpPkVhY2ggaW50ZWdlciAxLTkgbXVzdCBhcHBlYXIgaW4gZWFjaCAzeDMgc3F1YXJlIGV4YWN0bHkgb25jZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgcHV6emxlIHRvIHRoZSByaWdodCBpcyBhIGNvcnJlY3RseS1jb21wbGV0ZWQgU3Vkb2t1IHB1enpsZS48XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgcmVjZW50bHkgYmVjb21lIG9ic2Vzc2VkIHdpdGggU3Vkb2t1IHB1enpsZXMgLSB5b3UgcGxheSB0aGVtIGFsbCB0aGUgdGltZSEgQnV0IHlvdSBoYXRlIHRoZSBmYWN0IHRoYXQgdGhlcmUgaXMgbm8gZWFzeSB3YXkgdG8gdmVyaWZ5IHRoYXQgeW91ciBwdXp6bGVzIGFyZSBjb21wbGV0ZWQgY29ycmVjdGx5LiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYW4gaWRlbnRpZnkgYSBjb3JyZWN0bHktY29tcGxldGVkIFN1ZG9rdSBib2FyZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgYmUgYSBzaW5nbGUgaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QtY2FzZSB3aWxsIGJlIDkgcm93cywgZWFjaCBjb250YWluaW5nIDkgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGJldHdlZW4gMSBhbmQgOS4gVGhlcmUgd2lsbCBiZSBvbmUgYmxhbmsgbGluZSBiZXR3ZWVuIGVhY2ggdGVzdCBjYXNlLjxcL3A+XHJcblxyXG48cD5UaGVyZSB3aWxsIGJlIGF0IG1vc3QgMTAwIHRlc3QgY2FzZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgb3V0cHV0IHRoZSBsaW5lICZsZHF1bztDYXNlIHg6JnJkcXVvOyB3aGVyZSB4IGlzIHRoZSBjYXNlIG51bWJlciwgb24gYSBzaW5nbGUgbGluZSBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlbiBwcmludCAmcmRxdW87Q09SUkVDVCZyZHF1bzsgaWYgdGhlIHB1enpsZSBpcyBzb2x2ZWQgY29ycmVjdGx5LCBhbmQgJnJkcXVvO0lOQ09SUkVDVCZyZHF1bzsgaWYgaXQgaXMgc29sdmVkIGluY29ycmVjdGx5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==