시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 590 224 166 40.686%

문제

최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한다.

시험은 N행 * M열 크기의 직사각형 교실에서 이루어진다. 교실은 1*1 크기의 단위 정사각형으로 이루어져 있는데, 각 단위 정사각형은 자리 하나를 의미한다.

최백준은 컨닝을 방지하기 위해서 다음과 같은 전략을 세웠다. 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위, 이렇게 총 네 자리에 앉아있는 친구의 답지를 항상 베낀다고 가정한다. 따라서, 자리 배치는 모든 학생이 컨닝을 할 수 없도록 배치되어야 한다.

위의 그림을 보자. A , C , D 혹은 E에 다른 학생을 앉히는 것은 좋은 생각이 아니다. 그 이유는 이미 앉아있는 학생이 그들의 답안지를 베낄 우려가 있기 때문이다. 하지만, B에 다른 학생을 앉힌다면, 두 학생은 서로의 답지를 베낄 수 없어 컨닝의 우려가 없다.

위와 같이 컨닝이 불가능하도록 자리를 배치 하려는 최백준의 행동에 분노한 일부 학생들이 교실의 책상을 부셔버렸기 때문에, 일부 자리에는 학생이 앉을 수 없다.

최백준은 교실의 모양이 주어졌을 때, 이 곳에서 아무도 컨닝을 할 수 없도록 학생을 배치하였을 경우에 교실에 배치할 수 있는 최대 학생 수가 몇 명인지 궁금해졌다. 최백준을 위해 이를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트케이스의 개수 C가 주어진다. 각각의 테스트 케이스는 아래와 같이 두 부분으로 이루어진다.

첫 번째 부분에서는 교실의 세로길이 N과 가로길이 M이 한 줄에 주어진다. (1 ≤ M ≤ 80, 1 ≤ N ≤ 80)

두 번째 부분에서는 정확하게 N줄이 주어진다. 그리고 각 줄은 M개의 문자로 이루어져있다. 모든 문자는 ‘.’(앉을 수 있는 자리) 또는 ‘x’(앉을 수 없는 자리, 소문자)로 구성된다.

출력

각각의 테스트 케이스에 대해 그 교실에서 시험을 볼 수 있는 최대 학생의 수를 출력한다.

예제 입력 1

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

예제 출력 1

4
1
2
46
W3sicHJvYmxlbV9pZCI6IjExMDE0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZWU4XHViMmRkIDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2Q1Y1x1YmMzMVx1YzkwMFx1Yzc0MCBcdWMxMWNcdWFjMTVcdWIzMDBcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgJmxkcXVvO1x1Y2VlOFx1YjJkZFx1Yzc1OCBcdWFlMzBcdWMyMjAmcmRxdW87XHVjNzc0XHViNzdjXHViMjk0IFx1YWNmY1x1YmFhOVx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNlNThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhY2ZjXHViYWE5XHVjNzQwIFx1YzBjMVx1YjJmOVx1ZDc4OCBcdWFlNGNcdWIyZTRcdWI4NmRcdWFlMzBcdWI4NWMgXHVjODE1XHVkM2M5XHVjNzc0IFx1YjA5OFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YmE4N1x1YmE4NyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjMmRjXHVkNWQ4XHVjNzQ0IFx1YmNmNFx1YjI5NCBcdWIzYzRcdWM5MTFcdWM1ZDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWIyZjVcdWM5YzBcdWI5N2MgXHViY2EwXHViMDdjXHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVkNWQ4XHVjNzQwIE5cdWQ1ODkgKiBNXHVjNWY0IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVhZDUwXHVjMmU0XHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhZDUwXHVjMmU0XHVjNzQwIDEqMSBcdWQwNmNcdWFlMzBcdWM3NTggXHViMmU4XHVjNzA0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDEgXHViMmU4XHVjNzA0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM3OTBcdWI5YWMgXHVkNTU4XHViMDk4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHViYzMxXHVjOTAwXHVjNzQwIFx1Y2VlOFx1YjJkZFx1Yzc0NCBcdWJjMjlcdWM5YzBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjODA0XHViN2I1XHVjNzQ0IFx1YzEzOFx1YzZlMFx1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzY3Y1x1Y2FiZCBcdWIzMDBcdWFjMDFcdWMxMjAgXHVjNzA0LCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViMzAwXHVhYzAxXHVjMTIwIFx1YzcwNCwgXHVjNzc0XHViODA3XHVhYzhjIFx1Y2QxZCBcdWIxMjQgXHVjNzkwXHViOWFjXHVjNWQwIFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjI5NCBcdWNlNWNcdWFkNmNcdWM3NTggXHViMmY1XHVjOWMwXHViOTdjIFx1ZDU2ZFx1YzBjMSBcdWJjYTBcdWIwODBcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1Yzc5MFx1YjlhYyBcdWJjMzBcdWNlNThcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWNlZThcdWIyZGRcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIzYzRcdWI4NWQgXHViYzMwXHVjZTU4XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcLzIwMTAwM1wvY3VubmluZy5KUEdcIiBzdHlsZT1cImhlaWdodDoxMjRweDsgd2lkdGg6MTgzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0NCBcdWJjZjRcdWM3OTAuIEEgLCBDICwgRCBcdWQ2MzlcdWM3NDAgRVx1YzVkMCBcdWIyZTRcdWI5NzggXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YzU0OVx1ZDc4OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjODhiXHVjNzQwIFx1YzBkZFx1YWMwMVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVjNzc0XHViYmY4IFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVhZGY4XHViNGU0XHVjNzU4IFx1YjJmNVx1YzU0OFx1YzljMFx1Yjk3YyBcdWJjYTBcdWIwODQgXHVjNmIwXHViODI0XHVhYzAwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgQlx1YzVkMCBcdWIyZTRcdWI5NzggXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YzU0OVx1ZDc4Y1x1YjJlNFx1YmE3NCwgXHViNDUwIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWMxMWNcdWI4NWNcdWM3NTggXHViMmY1XHVjOWMwXHViOTdjIFx1YmNhMFx1YjA4NCBcdWMyMTggXHVjNWM2XHVjNWI0IFx1Y2VlOFx1YjJkZFx1Yzc1OCBcdWM2YjBcdWI4MjRcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Y2VlOFx1YjJkZFx1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIzYzRcdWI4NWQgXHVjNzkwXHViOWFjXHViOTdjIFx1YmMzMFx1Y2U1OCBcdWQ1NThcdWI4MjRcdWIyOTQgXHVjZDVjXHViYzMxXHVjOTAwXHVjNzU4IFx1ZDU4OVx1YjNkOVx1YzVkMCBcdWJkODRcdWIxNzhcdWQ1NWMgXHVjNzdjXHViZDgwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWFkNTBcdWMyZTRcdWM3NTggXHVjYzQ1XHVjMGMxXHVjNzQ0IFx1YmQ4MFx1YzE1NFx1YmM4NFx1YjgzOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3Y1x1YmQ4MCBcdWM3OTBcdWI5YWNcdWM1ZDBcdWIyOTQgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzU0OVx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWJjMzFcdWM5MDBcdWM3NDAgXHVhZDUwXHVjMmU0XHVjNzU4IFx1YmFhOFx1YzU5MVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhY2YzXHVjNWQwXHVjMTFjIFx1YzU0NFx1YmIzNFx1YjNjNCBcdWNlZThcdWIyZGRcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIzYzRcdWI4NWQgXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YzYwMFx1Yzc0NCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVhZDUwXHVjMmU0XHVjNWQwIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NTlcdWMwZGQgXHVjMjE4XHVhYzAwIFx1YmE4NyBcdWJhODVcdWM3NzhcdWM5YzAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LiBcdWNkNWNcdWJjMzFcdWM5MDBcdWM3NDQgXHVjNzA0XHVkNTc0IFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQmbmJzcDtcdWI0NTAgXHViZDgwXHViZDg0XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJkODBcdWJkODRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVhZDUwXHVjMmU0XHVjNzU4IFx1YzEzOFx1Yjg1Y1x1YWUzOFx1Yzc3NCBOXHVhY2ZjIFx1YWMwMFx1Yjg1Y1x1YWUzOFx1Yzc3NCBNXHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygxICZsZTsgTSAmbGU7IDgwLCAxICZsZTsgTiAmbGU7IDgwKTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YmQ4MFx1YmQ4NFx1YzVkMFx1YzExY1x1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgTlx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjMDEgXHVjOTA0XHVjNzQwIE1cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YmIzOFx1Yzc5MFx1YjI5NCZuYnNwOzxzdHJvbmc+JmxzcXVvOy4mcnNxdW87PFwvc3Ryb25nPihcdWM1NDlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWI5YWMpIFx1YjYxMFx1YjI5NCZuYnNwOzxzdHJvbmc+JmxzcXVvO3gmcnNxdW87PFwvc3Ryb25nPihcdWM1NDlcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWM3OTBcdWI5YWMsIFx1YzE4Y1x1YmIzOFx1Yzc5MClcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWFkZjggXHVhZDUwXHVjMmU0XHVjNWQwXHVjMTFjIFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTEwMTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJObyBDaGVhdGluZyAoTGFyZ2UpIiwiZGVzY3JpcHRpb24iOiI8cD5BIGxvY2FsIGhpZ2ggc2Nob29sIGlzIGdvaW5nIHRvIGhvbGQgYSBmaW5hbCBleGFtIGluIGEgYmlnIGNsYXNzcm9vbS4gSG93ZXZlciwgc29tZSBzdHVkZW50cyBpbiB0aGlzIHNjaG9vbCBhcmUgYWx3YXlzIHRyeWluZyB0byBzZWUgZWFjaCBvdGhlciYjMzk7cyBhbnN3ZXIgc2hlZXQgZHVyaW5nIGV4YW1zITxcL3A+XHJcblxyXG48cD5UaGUgY2xhc3Nyb29tIGNhbiBiZSByZWdhcmRlZCBhcyBhIHJlY3RhbmdsZSBvZiZuYnNwOzxzdHJvbmc+TTxcL3N0cm9uZz4mbmJzcDtyb3dzIGJ5Jm5ic3A7PHN0cm9uZz5OPFwvc3Ryb25nPiZuYnNwO2NvbHVtbnMgb2YgdW5pdCBzcXVhcmVzLCB3aGVyZSBlYWNoIHVuaXQgc3F1YXJlIHJlcHJlc2VudHMgYSBzZWF0LjxcL3A+XHJcblxyXG48cD5UaGUgc2Nob29sIHByaW5jaXBhbCBkZWNpZGVkIHRvIHNldCB0aGUgZm9sbG93aW5nIHJ1bGUgdG8gcHJldmVudCBjaGVhdGluZzo8YnIgXC8+XHJcbkFzc3VtZSBhIHN0dWRlbnQgaXMgYWJsZSB0byBzZWUgaGlzIGxlZnQsIHJpZ2h0LCB1cHBlci1sZWZ0LCBhbmQgdXBwZXItcmlnaHQgbmVpZ2hib3JzJiMzOTsgYW5zd2VyIHNoZWV0cy4gVGhlIGFzc2lnbm1lbnQgb2Ygc2VhdHMgbXVzdCBndWFyYW50ZWUgdGhhdCBub2JvZHkmIzM5O3MgYW5zd2VyIHNoZWV0IGNhbiBiZSBzZWVuIGJ5IGFueSBvdGhlciBzdHVkZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMjcwMFwvY3VubmluZy5qcGdcIiBcLz48XC9wPlxyXG5cclxuPHA+QXMgaW4gdGhpcyBwaWN0dXJlLCBpdCB3aWxsIG5vdCBiZSBhIGdvb2QgaWRlYSB0byBzZWF0IGFueW9uZSBpbiBBLCBDLCBELCBvciBFIGJlY2F1c2UgdGhlIGJveSBpbiB0aGUgYmFjayByb3cgd291bGQgYmUgYWJsZSB0byBzZWUgdGhlaXIgYW5zd2VyIHNoZWV0cy4gSG93ZXZlciwgaWYgdGhlcmUgaXMgYSBnaXJsIHNpdHRpbmcgaW4gQiwgaGUgd2lsbCBub3QgYmUgYWJsZSB0byBzZWUgaGVyIGFuc3dlciBzaGVldC48XC9wPlxyXG5cclxuPHA+U29tZSBzZWF0cyBpbiB0aGUgY2xhc3Nyb29tIGFyZSBicm9rZW4sIGFuZCB3ZSBjYW5ub3QgcHV0IGEgc3R1ZGVudCBpbiBhIGJyb2tlbiBzZWF0LjxcL3A+XHJcblxyXG48cD5UaGUgcHJpbmNpcGFsIGFza2VkIHlvdSB0byBhbnN3ZXIgdGhlIGZvbGxvd2luZyBxdWVzdGlvbjogV2hhdCBpcyB0aGUgbWF4aW11bSBudW1iZXIgb2Ygc3R1ZGVudHMgdGhhdCBjYW4gYmUgcGxhY2VkIGluIHRoZSBjbGFzc3Jvb20gc28gdGhhdCBubyBvbmUgY2FuIGNoZWF0PzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZ2l2ZXMgdGhlIG51bWJlciBvZiBjYXNlcywmbmJzcDs8c3Ryb25nPkM8XC9zdHJvbmc+LiZuYnNwOzxzdHJvbmc+QzxcL3N0cm9uZz4mbmJzcDt0ZXN0IGNhc2VzIGZvbGxvdy4gRWFjaCBjYXNlIGNvbnNpc3RzIG9mIHR3byBwYXJ0cy48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IHBhcnQgaXMgYSBzaW5nbGUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyZuYnNwOzxzdHJvbmc+TTxcL3N0cm9uZz4mbmJzcDthbmQmbmJzcDs8c3Ryb25nPk48XC9zdHJvbmc+OiBUaGUgaGVpZ2h0IGFuZCB3aWR0aCBvZiB0aGUgcmVjdGFuZ3VsYXIgY2xhc3Nyb29tLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIHBhcnQgd2lsbCBiZSBleGFjdGx5Jm5ic3A7PHN0cm9uZz5NPFwvc3Ryb25nPiZuYnNwO2xpbmVzLCB3aXRoIGV4YWN0bHkmbmJzcDs8c3Ryb25nPk48XC9zdHJvbmc+Jm5ic3A7Y2hhcmFjdGVycyBpbiBlYWNoIG9mIHRoZXNlIGxpbmVzLiBFYWNoIGNoYXJhY3RlciBpcyBlaXRoZXIgYSAmIzM5Oy4mIzM5OyAodGhlIHNlYXQgaXMgbm90IGJyb2tlbikgb3IgJiMzOTt4JiMzOTsgKHRoZSBzZWF0IGlzIGJyb2tlbiwgbG93ZXJjYXNlIHgpLjxcL3A+XHJcblxyXG48cD5MaW1pdHM8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48c3Ryb25nPkM8XC9zdHJvbmc+Jm5ic3A7PSAyMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsmbmJzcDs8c3Ryb25nPk08XC9zdHJvbmc+Jm5ic3A7JmxlOyA4MDxcL2xpPlxyXG5cdDxsaT4xICZsZTsmbmJzcDs8c3Ryb25nPk48XC9zdHJvbmc+Jm5ic3A7JmxlOyA4MDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyAmcXVvdDtDYXNlICM8c3Ryb25nPlg8XC9zdHJvbmc+OiZuYnNwOzxzdHJvbmc+WTxcL3N0cm9uZz4mcXVvdDssIHdoZXJlJm5ic3A7PHN0cm9uZz5YPFwvc3Ryb25nPiZuYnNwO2lzIHRoZSBjYXNlIG51bWJlciwgc3RhcnRpbmcgZnJvbSAxLCBhbmQmbmJzcDs8c3Ryb25nPlk8XC9zdHJvbmc+Jm5ic3A7aXMgdGhlIG1heGltdW0gcG9zc2libGUgbnVtYmVyIG9mIHN0dWRlbnRzIHRoYXQgY2FuIHRha2UgdGhlIGV4YW0gaW4gdGhlIGNsYXNzcm9vbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Google Code Jam > Google Code Jam 2008 > Round 3 C2번

비슷한 문제