시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 38 36 76.596%

문제

남규는 재우와 틱택토를 하던 도중, 거의 이기기 직전에 다다랐다! 남규의 승리로부터 단 한 단계 전의 틱택토 게임판이 주어졌을 때, 승리를 위해 말을 어디에 놓아야 할지 알아내자.

입력

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

각 테스트 케이스는 현재 틱택토 게임판의 상태를 3줄에 걸쳐 나타내며, 그 다음 줄에는 남규의 말(x 또는 o)이 무엇인지가 주어진다. 게임판의 상태는 'x', 'o', '-'(빈칸)으로 이루어진다. 반드시 다음 한 번의 행동으로 남규가 게임을 이길 수 있는 상태만 주어진다.

출력

각 테스트 케이스마다 "Case x:"와 공백을 출력한 후, 아래의 3줄에 걸쳐 남규가 다음 한 수로 이긴 후 게임판의 상태를 출력한다. x는 테스트 케이스의 번호이며, 1부터 시작한다.

예제 입력 1

3
o--
-o-
xx-
x
o-x
--o
x--
x
xx-
o-o
---
o

예제 출력 1

Case 1:
o--
-o-
xxx
Case 2:
o-x
-xo
x--
Case 3:
xx-
ooo
---
W3sicHJvYmxlbV9pZCI6IjkyOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyZjFcdWQwZGRcdWQxYTAgXHVjNzc0XHVhZTMwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC85MjkwXC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojk0cHg7IHdpZHRoOjYwOHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjBhOFx1YWRkY1x1YjI5NCBcdWM3YWNcdWM2YjBcdWM2NDAgXHVkMmYxXHVkMGRkXHVkMWEwXHViOTdjIFx1ZDU1OFx1YjM1OCBcdWIzYzRcdWM5MTEsIFx1YWM3MFx1Yzc1OCBcdWM3NzRcdWFlMzBcdWFlMzAgXHVjOWMxXHVjODA0XHVjNWQwIFx1YjJlNFx1YjJlNFx1Yjc5MFx1YjJlNCEgXHViMGE4XHVhZGRjXHVjNzU4IFx1YzJiOVx1YjlhY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWIyZTggXHVkNTVjIFx1YjJlOFx1YWNjNCBcdWM4MDRcdWM3NTggXHVkMmYxXHVkMGRkXHVkMWEwIFx1YWM4Y1x1Yzc4NFx1ZDMxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMyYjlcdWI5YWNcdWI5N2MgXHVjNzA0XHVkNTc0IFx1YjlkMFx1Yzc0NCBcdWM1YjRcdWI1MTRcdWM1ZDAgXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDU2MFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDYwNFx1YzdhYyBcdWQyZjFcdWQwZGRcdWQxYTAgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyAzXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjBhOFx1YWRkY1x1Yzc1OCBcdWI5ZDAoeCBcdWI2MTBcdWIyOTQgbylcdWM3NzQgXHViYjM0XHVjNWM3XHVjNzc4XHVjOWMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCAmIzM5O3gmIzM5OywgJiMzOTtvJiMzOTssICYjMzk7LSYjMzk7KFx1YmU0OFx1Y2U3OClcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjMThcdWI0ZGNcdWMyZGMgXHViMmU0XHVjNzRjIFx1ZDU1YyBcdWJjODhcdWM3NTggXHVkNTg5XHViM2Q5XHVjNzNjXHViODVjIFx1YjBhOFx1YWRkY1x1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGMxXHVkMGRjXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAmcXVvdDtDYXNlIHg6JnF1b3Q7XHVjNjQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVkNmM0LCBcdWM1NDRcdWI3OThcdWM3NTggM1x1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViMGE4XHVhZGRjXHVhYzAwIFx1YjJlNFx1Yzc0YyBcdWQ1NWMgXHVjMjE4XHViODVjIFx1Yzc3NFx1YWUzNCBcdWQ2YzQgXHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIHhcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWJhNzAsIDFcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkyOTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaWMgVGFjIFRvZSBGb3IgdGhlIFdpbiIsImRlc2NyaXB0aW9uIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvOTI5MFwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDo5NHB4OyB3aWR0aDo2MDhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHBsYXlpbmcgYSBnYW1lIG9mIHRpYy10YWMtdG9lIHdpdGggeW91ciBmcmllbmQgYW5kIHlvdSBhcmUgYWJvdXQgdG8gd2luISBHaXZlbiBhIHRpYy10YWMtdG9lIGJvYXJkIHRoYXQgaXMgb25lIHN0ZXAgYXdheSBmcm9tIHZpY3RvcnksIG1ha2UgdGhlIHdpbm5pbmcgbW92ZSE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgYmUgdGhlIG51bWJlciBvZiBnYW1lcyB0aGF0IHlvdSBhcmUgcGxheWluZy4gRWFjaCBnYW1lIGJvYXJkIHdpbGwgY29tZSBpbiAzeDMgYmxvY2tzIG9mIGNoYXJhY3RlcnMsIHdoZXJlIHggYW5kIG8gYXJlIHBsYXllcnMmcnNxdW87IG1hcmtlcnMsIGFuZCBhIGRhc2ggKC0pIHJlcHJlc2VudHMgYW4gb3BlbiBzcXVhcmUuIEVhY2ggYm9hcmQgd2lsbCBiZSBmb2xsb3dlZCBieSBhIHNpbmdsZSB4IG9yIG8gdG8gcmVwcmVzZW50IHdoaWNoIHBsYXllciB5b3UgYXJlLiBZb3Ugd2lsbCBoYXZlIG9ubHkgdHdvIG9mIHlvdXIgbWFya2VycyBvbiB0aGUgYm9hcmQsIGFuZCB5b3UgYXJlIGd1YXJhbnRlZWQgdG8gYmUgYWJsZSB0byB3aW4gdGhlIGdhbWUgaW4gb25lIG1vdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgb3V0cHV0IHRoZSBsaW5lICZsZHF1bztDYXNlIHg6JnJkcXVvOyB3aGVyZSB4IGlzIHRoZSBjYXNlIG51bWJlciwgb24gYSBzaW5nbGUgbGluZS4gT24gdGhlIG5leHQgMyBsaW5lcywgb3V0cHV0IHRoZSBib2FyZCBhcyBpdCB3aWxsIGxvb2sgYWZ0ZXIgeW91ciB3aW5uaW5nIG1vdmUuIFVzZSB4IGFuZCBvIHRvIHJlcHJlc2VudCBwbGF5ZXJzJnJzcXVvOyBtYXJrZXJzIGFuZCBhIGRhc2ggKC0pIHRvIHJlcHJlc2VudCBvcGVuIHNxdWFyZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d