시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB83642929214546.855%

문제

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

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

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

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

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

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

입력

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

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

두 번째 부분에서는 정확하게 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
W3sicHJvYmxlbV9pZCI6IjEwMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZThcdWIyZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2Q1Y1x1YmMzMVx1YzkwMFx1Yzc0MCBcdWMxMWNcdWFjMTVcdWIzMDBcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgJmxkcXVvO1x1Y2VlOFx1YjJkZFx1Yzc1OCBcdWFlMzBcdWMyMjAmcmRxdW87XHVjNzc0XHViNzdjXHViMjk0IFx1YWNmY1x1YmFhOVx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNlNThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhY2ZjXHViYWE5XHVjNzQwIFx1YzBjMVx1YjJmOVx1ZDc4OCBcdWFlNGNcdWIyZTRcdWI4NmRcdWFlMzBcdWI4NWMgXHVjODE1XHVkM2M5XHVjNzc0IFx1YjA5OFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YmE4N1x1YmE4NyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjMmRjXHVkNWQ4XHVjNzQ0IFx1YmNmNFx1YjI5NCBcdWIzYzRcdWM5MTFcdWM1ZDAgXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWIyZjVcdWM5YzBcdWI5N2MgXHViY2EwXHViMDdjXHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVkNWQ4XHVjNzQwIE5cdWQ1ODksJm5ic3A7TVx1YzVmNCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YWQ1MFx1YzJlNFx1YzVkMFx1YzExYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWQ1MFx1YzJlNFx1Yzc0MCAxJnRpbWVzOzEgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVhYzAxIFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVjNzkwXHViOWFjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2Q1Y1x1YmMzMVx1YzkwMFx1Yzc0MCBcdWNlZThcdWIyZGRcdWM3NDQgXHViYzI5XHVjOWMwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWMxMzhcdWM2ZTBcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM2N2NcdWNhYmQgXHViMzAwXHVhYzAxXHVjMTIwIFx1YzcwNCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjMwMFx1YWMwMVx1YzEyMCBcdWM3MDQsIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWNkMWQgXHViMTI0IFx1Yzc5MFx1YjlhY1x1YzVkMCBcdWM1NDlcdWM1NDRcdWM3ODhcdWIyOTQgXHVjZTVjXHVhZDZjXHVjNzU4IFx1YjJmNVx1YzljMFx1Yjk3YyBcdWQ1NmRcdWMwYzEgXHViY2EwXHViMDgwXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM3OTBcdWI5YWMgXHViYzMwXHVjZTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjZWU4XHViMmRkXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViM2M0XHViODVkIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC8yMDEwMDNcL2N1bm5pbmcuSlBHXCIgc3R5bGU9XCJoZWlnaHQ6MTI0cHg7IHdpZHRoOjE4M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDQgXHViY2Y0XHVjNzkwLiBBLCBDLCBEIFx1ZDYzOVx1Yzc0MCBFXHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHVjNTQ5XHVkNzg4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWM4OGJcdWM3NDAgXHVjMGRkXHVhYzAxXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWM3NzRcdWJiZjggXHVjNTQ5XHVjNTQ0XHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWFkZjhcdWI0ZTRcdWM3NTggXHViMmY1XHVjNTQ4XHVjOWMwXHViOTdjIFx1YmNhMFx1YjA4NCBcdWM2YjBcdWI4MjRcdWFjMDAgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBCXHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHVjNTQ5XHVkNzhjXHViMmU0XHViYTc0LCBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzQwIFx1YzExY1x1Yjg1Y1x1Yzc1OCBcdWIyZjVcdWM5YzBcdWI5N2MgXHViY2EwXHViMDg0IFx1YzIxOCBcdWM1YzZcdWM1YjQgXHVjZWU4XHViMmRkXHVjNzU4IFx1YzZiMFx1YjgyNFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjZWU4XHViMmRkXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzMwXHVjZTU4IFx1ZDU1OFx1YjgyNFx1YjI5NCBcdWNkNWNcdWJjMzFcdWM5MDBcdWM3NTggXHVkNTg5XHViM2Q5XHVjNWQwIFx1YmQ4NFx1YjE3OFx1ZDU1YyBcdWM3N2NcdWJkODAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YWQ1MFx1YzJlNFx1Yzc1OCBcdWNjNDVcdWMwYzFcdWM3NDQgXHViZDgwXHVjMjM0XHViYzg0XHViODM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzdjXHViZDgwIFx1Yzc5MFx1YjlhY1x1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNTQ5XHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2Q1Y1x1YmMzMVx1YzkwMFx1Yzc0MCBcdWFkNTBcdWMyZTRcdWM3NTggXHViYWE4XHVjNTkxXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWFjZjNcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViYjM0XHViM2M0IFx1Y2VlOFx1YjJkZFx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjNjNFx1Yjg1ZCBcdWQ1NTlcdWMwZGRcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTU4XHVjNjAwXHVjNzQ0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWFkNTBcdWMyZTRcdWM1ZDAgXHViYzMwXHVjZTU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1OVx1YzBkZCBcdWMyMThcdWFjMDAgXHViYTg3IFx1YmE4NVx1Yzc3OFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1Y2Q1Y1x1YmMzMVx1YzkwMFx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCZuYnNwO1x1YjQ1MCBcdWJkODBcdWJkODRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YmQ4MFx1YmQ4NFx1YzVkMFx1YzExY1x1YjI5NCBcdWFkNTBcdWMyZTRcdWM3NTggXHVjMTM4XHViODVjXHVhZTM4XHVjNzc0IE5cdWFjZmMgXHVhYzAwXHViODVjXHVhZTM4XHVjNzc0IE1cdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEmbmJzcDsmbGU7IE0gJmxlOyAxMCwgMSAmbGU7IE4gJmxlOyAxMCk8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWJkODBcdWJkODRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIE5cdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzAxIFx1YzkwNFx1Yzc0MCBNXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJiMzhcdWM3OTBcdWIyOTQgPHN0cm9uZz4mbHNxdW87LiZyc3F1bzs8XC9zdHJvbmc+KFx1YzU0OVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc5MFx1YjlhYykgXHViNjEwXHViMjk0IDxzdHJvbmc+JmxzcXVvO3gmcnNxdW87PFwvc3Ryb25nPihcdWM1NDlcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWM3OTBcdWI5YWMsIFx1YzE4Y1x1YmIzOFx1Yzc5MClcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWFkZjggXHVhZDUwXHVjMmU0XHVjNWQwXHVjMTFjIFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTAxNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5vIENoZWF0aW5nIChTbWFsbCkiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbG9jYWwgaGlnaCBzY2hvb2wgaXMgZ29pbmcgdG8gaG9sZCBhIGZpbmFsIGV4YW0gaW4gYSBiaWcgY2xhc3Nyb29tLiBIb3dldmVyLCBzb21lIHN0dWRlbnRzIGluIHRoaXMgc2Nob29sIGFyZSBhbHdheXMgdHJ5aW5nIHRvIHNlZSBlYWNoIG90aGVyJiMzOTtzIGFuc3dlciBzaGVldCBkdXJpbmcgZXhhbXMhPFwvcD5cclxuXHJcbjxwPlRoZSBjbGFzc3Jvb20gY2FuIGJlIHJlZ2FyZGVkIGFzIGEgcmVjdGFuZ2xlIG9mJm5ic3A7PHN0cm9uZz5NPFwvc3Ryb25nPiZuYnNwO3Jvd3MgYnkmbmJzcDs8c3Ryb25nPk48XC9zdHJvbmc+Jm5ic3A7Y29sdW1ucyBvZiB1bml0IHNxdWFyZXMsIHdoZXJlIGVhY2ggdW5pdCBzcXVhcmUgcmVwcmVzZW50cyBhIHNlYXQuPFwvcD5cclxuXHJcbjxwPlRoZSBzY2hvb2wgcHJpbmNpcGFsIGRlY2lkZWQgdG8gc2V0IHRoZSBmb2xsb3dpbmcgcnVsZSB0byBwcmV2ZW50IGNoZWF0aW5nOjxiciBcLz5cclxuQXNzdW1lIGEgc3R1ZGVudCBpcyBhYmxlIHRvIHNlZSBoaXMgbGVmdCwgcmlnaHQsIHVwcGVyLWxlZnQsIGFuZCB1cHBlci1yaWdodCBuZWlnaGJvcnMmIzM5OyBhbnN3ZXIgc2hlZXRzLiBUaGUgYXNzaWdubWVudCBvZiBzZWF0cyBtdXN0IGd1YXJhbnRlZSB0aGF0IG5vYm9keSYjMzk7cyBhbnN3ZXIgc2hlZXQgY2FuIGJlIHNlZW4gYnkgYW55IG90aGVyIHN0dWRlbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzEyNjk5XC9jdW5uaW5nLmpwZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5BcyBpbiB0aGlzIHBpY3R1cmUsIGl0IHdpbGwgbm90IGJlIGEgZ29vZCBpZGVhIHRvIHNlYXQgYW55b25lIGluIEEsIEMsIEQsIG9yIEUgYmVjYXVzZSB0aGUgYm95IGluIHRoZSBiYWNrIHJvdyB3b3VsZCBiZSBhYmxlIHRvIHNlZSB0aGVpciBhbnN3ZXIgc2hlZXRzLiBIb3dldmVyLCBpZiB0aGVyZSBpcyBhIGdpcmwgc2l0dGluZyBpbiBCLCBoZSB3aWxsIG5vdCBiZSBhYmxlIHRvIHNlZSBoZXIgYW5zd2VyIHNoZWV0LjxcL3A+XHJcblxyXG48cD5Tb21lIHNlYXRzIGluIHRoZSBjbGFzc3Jvb20gYXJlIGJyb2tlbiwgYW5kIHdlIGNhbm5vdCBwdXQgYSBzdHVkZW50IGluIGEgYnJva2VuIHNlYXQuPFwvcD5cclxuXHJcbjxwPlRoZSBwcmluY2lwYWwgYXNrZWQgeW91IHRvIGFuc3dlciB0aGUgZm9sbG93aW5nIHF1ZXN0aW9uOiBXaGF0IGlzIHRoZSBtYXhpbXVtIG51bWJlciBvZiBzdHVkZW50cyB0aGF0IGNhbiBiZSBwbGFjZWQgaW4gdGhlIGNsYXNzcm9vbSBzbyB0aGF0IG5vIG9uZSBjYW4gY2hlYXQ/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBnaXZlcyB0aGUgbnVtYmVyIG9mIGNhc2VzLCZuYnNwOzxzdHJvbmc+QzxcL3N0cm9uZz4uJm5ic3A7PHN0cm9uZz5DPFwvc3Ryb25nPiZuYnNwO3Rlc3QgY2FzZXMgZm9sbG93LiBFYWNoIGNhc2UgY29uc2lzdHMgb2YgdHdvIHBhcnRzLjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgcGFydCBpcyBhIHNpbmdsZSBsaW5lIHdpdGggdHdvIGludGVnZXJzJm5ic3A7PHN0cm9uZz5NPFwvc3Ryb25nPiZuYnNwO2FuZCZuYnNwOzxzdHJvbmc+TjxcL3N0cm9uZz46IFRoZSBoZWlnaHQgYW5kIHdpZHRoIG9mIHRoZSByZWN0YW5ndWxhciBjbGFzc3Jvb20uPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgcGFydCB3aWxsIGJlIGV4YWN0bHkmbmJzcDs8c3Ryb25nPk08XC9zdHJvbmc+Jm5ic3A7bGluZXMsIHdpdGggZXhhY3RseSZuYnNwOzxzdHJvbmc+TjxcL3N0cm9uZz4mbmJzcDtjaGFyYWN0ZXJzIGluIGVhY2ggb2YgdGhlc2UgbGluZXMuIEVhY2ggY2hhcmFjdGVyIGlzIGVpdGhlciBhICYjMzk7LiYjMzk7ICh0aGUgc2VhdCBpcyBub3QgYnJva2VuKSBvciAmIzM5O3gmIzM5OyAodGhlIHNlYXQgaXMgYnJva2VuLCBsb3dlcmNhc2UgeCkuPFwvcD5cclxuXHJcbjxwPkxpbWl0czxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxzdHJvbmc+QzxcL3N0cm9uZz4mbmJzcDs9IDIwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyZuYnNwOzxzdHJvbmc+TTxcL3N0cm9uZz4mbmJzcDsmbGU7IDEwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyZuYnNwOzxzdHJvbmc+TjxcL3N0cm9uZz4mbmJzcDsmbGU7IDEwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nICZxdW90OzxzdHJvbmc+WTxcL3N0cm9uZz4mcXVvdDssIHdoZXJlJm5ic3A7PHN0cm9uZz5ZPFwvc3Ryb25nPiZuYnNwO2lzIHRoZSBtYXhpbXVtIHBvc3NpYmxlIG51bWJlciBvZiBzdHVkZW50cyB0aGF0IGNhbiB0YWtlIHRoZSBleGFtIGluIHRoZSBjbGFzc3Jvb20uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

비슷한 문제