시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 46 26 13 54.167%

문제

N x N 보드에 테러범들이 지뢰를 설치해 놓았다. 다행히도 가장자리 칸에는 지뢰가 없는 것으로 확인되어 지뢰 탐지기를 설치했다. 지뢰 탐지기는 주변에 몇 개의 지뢰가 있는지를 보여준다. 즉, 가장자리 칸의 숫자는 인접한 칸에 있는 지뢰의 개수를 나타낸다.

111000
2####0
3####1
3####1
2####1
112110

위 그림은 6 x 6 보드를 나타낸다. 이 보드에는 최대 10개의 지뢰가 놓일 수 있다.

111000
2*###0
3***#1
3****1
2*#*#1
112110

주어진 보드에 놓일 수 있는 최대 지뢰 개수를 출력하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 보드의 크기 N(1 ≤ N ≤ 100)이 주어지고 두 번째 줄부터는 보드를 나타내는 N개의 문자열이 주어진다. 각 문자열의 길이는 N이다.

출력

각 테스트 케이스에 대해서 보드에 놓일 수 있는 최대 지뢰의 개수를 한 줄에 하나씩 출력한다.

예제 입력

3
6
111000
2####0
3####1
3####1
2####1
112110
5
11100
2###1
3###1
2###1
12210
7
1233210
1#####1
1#####1
1#####2
2#####2
2#####2
1232211

예제 출력

10
6
20

힌트

출처