시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 836 353 241 39.835%

문제

당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색에서 흰색으로, 혹은 흰색에서 검은색으로 변할 것이다.

당신은 모든 칸이 흰색인 3x3 보드를 입력으로 주어지는 보드의 형태로 바꾸려고 한다. 보드를 회전시킬수는 없다.

Figure D.1: 예제 입력

입력

첫 줄에는 테스트 케이스의 숫자 P(0 < P <= 50)이 주어진다.

각각의 테스트 케이스에 대해서 세 줄에 걸쳐 한 줄에 세 글자씩이 입력으로 들어온다. "*"은 검은색을 뜻하며 "."은 흰색을 뜻한다.

출력

각각의 테스트 케이스에 대해서 흰 보드를 입력에 주어진 보드로 바꾸는 데 필요한 최소 클릭의 회수를 구하여라.

예제 입력 1

2
*..
**.
*..
***
*..
..*

예제 출력 1

1
3
W3sicHJvYmxlbV9pZCI6IjEwNDcyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmVkXHVjNzkwXHViNGE0XHVjOWQxXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZjlcdWMyZTBcdWM1ZDBcdWFjOGMgM3gzIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjZTc4XHVjNzQwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWQ3NzBcdWMwYzkgXHVkNjM5XHVjNzQwIFx1YWM4MFx1Yzc0MFx1YzBjOVx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjZTc4XHVjNzQ0IFx1ZDA3NFx1YjlhZFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWIyZjlcdWMyZTBcdWM3NzQgXHVkMDc0XHViOWFkXHVkNTVjIFx1Y2U3OFx1YWNmYyBcdWFkZjggXHVjZTc4XHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWIzZDlcdWMxMWNcdWIwYThcdWJkODEgXHViMTI0IFx1Y2U3OFx1Yzc3NCAoXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0KSBcdWFjODBcdWM3NDBcdWMwYzlcdWM1ZDBcdWMxMWMgXHVkNzcwXHVjMGM5XHVjNzNjXHViODVjLCBcdWQ2MzlcdWM3NDAgXHVkNzcwXHVjMGM5XHVjNWQwXHVjMTFjIFx1YWM4MFx1Yzc0MFx1YzBjOVx1YzczY1x1Yjg1YyBcdWJjYzBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc3NCBcdWQ3NzBcdWMwYzlcdWM3NzggM3gzIFx1YmNmNFx1YjRkY1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViYzE0XHVhZmI4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViY2Y0XHViNGRjXHViOTdjIFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhY1x1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mbGlwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4M3B4OyB3aWR0aDozMzlweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+RmlndXJlIEQuMTogXHVjNjA4XHVjODFjIFx1Yzc4NVx1YjgyNTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIyYlx1Yzc5MCBQKDAgJmx0OyBQICZsdDs9IDUwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWMxMzggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YzEzOCBcdWFlMDBcdWM3OTBcdWM1MjlcdWM3NzQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gJnF1b3Q7KiZxdW90O1x1Yzc0MCBcdWFjODBcdWM3NDBcdWMwYzlcdWM3NDQgXHViNzNiXHVkNTU4XHViYTcwICZxdW90Oy4mcXVvdDtcdWM3NDAgXHVkNzcwXHVjMGM5XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNzcwIFx1YmNmNFx1YjRkY1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmNmNFx1YjRkY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVkMDc0XHViOWFkXHVjNzU4IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0NzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGbGlwIEZpdmUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoaXMgaXMgYSBsb2dpYyBwdXp6bGUgaW4gd2hpY2ggeW91IGhhdmUgYSBzcXVhcmUgZ3JpZCBvZiAzJnRpbWVzOzMgY2VsbHMuIEVhY2ggY2VsbCBpcyBpbml0aWFsbHkgZWl0aGVyIHdoaXRlIG9yIGJsYWNrLiBXaGVuIHlvdSBjbGljayBvbiBhIHNxdWFyZSBpdCBmbGlwcywgb3IgdG9nZ2xlcywgdGhlIGNvbG9yIG9mIHRoYXQgc3F1YXJlIGFuZCB0aGUgY29sb3JzIG9mIGl0cyBmb3VyIGltbWVkaWF0ZSBub3J0aCwgc291dGgsIGVhc3QgYW5kIHdlc3QgbmVpZ2hib3JzIHRoYXQgZXhpc3QgKHRoZXkgZG9uJnJzcXVvO3QgZXhpc3QgaWYgdGhleSB3b3VsZCBiZSBvdXRzaWRlIHRoZSBncmlkKS48XC9wPlxyXG5cclxuPHA+VGhlIHByb2JsZW0gaXMgdG8gZmluZCB0aGUgbWluaW11bSBudW1iZXIgb2YgY2VsbCBjbGlja3MgdG8gdHJhbnNmb3JtIGEgZ3JpZCBvZiBhbGwgd2hpdGUgY2VsbHMgaW50byB0aGUgaW5wdXQgZ3JpZCAod2hpY2ggaXMgYWx3YXlzIHBvc3NpYmxlKS4gWW91IGNhbm5vdCByb3RhdGUgdGhlIGdyaWQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2ZsaXAucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgzcHg7IHdpZHRoOjMzOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPkZpZ3VyZSBELjE6IFRoZSB0d28gc2FtcGxlIHByb2JsZW1zPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgdmFsdWUgaW4gdGhlIGlucHV0IGZpbGUgaXMgYW4gaW50ZWdlciBQICgwICZsdDsgUCAmbGU7IDUwKSBvbiBhIGxpbmUgYnkgaXRzZWxmIGdpdmluZyB0aGUgbnVtYmVyIG9mIHByb2JsZW1zIHRvIHNvbHZlLjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBvZiB0aGUgUCBwcm9ibGVtcywgMyBsaW5lcyBvZiAzIGNoYXJhY3RlcnMgZGVzY3JpYmUgdGhlIGlucHV0IGdyaWQuIFRoZSBjaGFyYWN0ZXJzIGluIHRoZSBncmlkIGRlc2NyaXB0aW9ucyBhcmUgJmxzcXVvOyomcnNxdW87IChmb3IgYmxhY2spIGFuZCAmbHNxdW87LiZyc3F1bzsgKGZvciB3aGl0ZSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcHJvYmxlbSBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciBnaXZpbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNsaWNrcyBuZWNlc3NhcnkgdG8gdHJhbnNmb3JtIGEgZ3JpZCBvZiBhbGwgd2hpdGUgY2VsbHMgaW50byB0aGUgcGF0dGVybiBnaXZlbiBpbiB0aGUgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d