씨앗 봉지
면접 대비시간 제한1초메모리 제한1024 MB
정원 격자에서 씨앗을 뿌려야 하는 칸을 모두 덮는 3x3 씨앗 봉지의 최소 개수를 구합니다.
문제
정원에 할당한 공간을 보면서, 전체를 채우려면 씨앗을 몇 봉지 사야 할지 궁금해진다. 씨앗을 심는 방식이 특이해서 계산이 조금 복잡하다. 씨앗을 심으려면 봉지를 공중에 던지고, 씨앗은 사용자 주변의 3x3 정사각형 영역에 떨어진다. 정원의 배치와 작물을 키우고 싶은 칸이 주어질 때, 필요한 씨앗 봉지의 최소 개수를 구하라. 원하지 않는 곳에 씨앗이 떨어져도 괜찮다. 그런 칸에는 물을 주지 않으면 된다. 한 칸이 여러 봉지의 씨앗으로 겹쳐도 된다.
입력
첫 줄에는 데이터 세트의 개수 n이 주어진다. 각 데이터 세트는 정원의 한 변의 길이 s (1≤s≤8)로 시작한다. 이어지는 s줄에 정원의 배치가 주어진다. '.'은 씨앗을 뿌릴 필요가 없는 칸을, 'x'는 씨앗을 뿌려 작물을 키우고 싶은 칸을 나타낸다.
출력
각 테스트 케이스마다 정원을 가꾸는 데 필요한 씨앗 봉지의 최소 개수를 출력한다.