시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB64113311326.651%

문제

치노는 하트 모양의 라떼 아트를 만드는 연습을 하고 있다. 치노가 수없이 연습한 흔적을 우연히 보게 된 코코아는 그 중에서 하트 모양의 라떼 아트가 얼마나 있는지 궁금해졌다. 코코아를 위해 라떼 위의 크림이 하트 모양인지 판별하는 프로그램을 만들어주자.

이 문제에서 치노의 라떼 아트는 단위 정사각형으로 나누어진 2차원 격자 형식으로 주어진다. #는 크림으로 꽉 찬 정사각형, .는 크림이 없는 정사각형을 나타낸다.

또한 하트 모양의 정의는 다음과 같다. 두 개의 양의 정수 $N$과 $M$ ($0<M<N$)이 존재해서, $N\times N$ 정사각형의 네 구석 중 한 쪽에서 $M\times M$ 정사각형을 제거한 모양을 하트 모양으로 정의한다.

다음은 $N=5$, $M=2$인 경우에 해당하는 하트의 예시이다.

###..
###..
#####
#####
#####

정확히 하나의 위에서 정의한 모양의 크림이 라떼 위에 올려져 있는 경우에만 하트로 인정한다. 크림 안에 구멍이 뚫려 있거나 따로 떨어진 크림 덩어리가 여러 개인 경우(각각의 크림 덩어리가 하트 모양인 경우 포함)는 하트 모양으로 보지 않는다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1\le T\le 100$)

다음 줄부터 $T$개의 테스트 케이스가 아래와 같은 형식으로 주어진다.

테스트 케이스의 첫 번째 줄에 격자의 세로 길이 $R$과 가로 길이 $C$가 공백으로 구분되어 주어진다. ($2\le R, C\le 10$)

다음 $R$개의 줄에 격자의 $i$행을 나타내는 길이 $C$의 문자열이 주어진다. 각 문자열은 # 또는 .로만 구성된다.

출력

각 테스트 케이스에 대해, 주어진 라떼 아트가 하트 모양이면 1, 아니면 0을 한 줄에 하나씩 출력한다.

예제 입력 1

3
5 5
###..
###..
#####
#####
#####
10 10
...#.#....
..#.#.#...
..#.#.#...
..#####...
.#.....#..
.#.#.#.#..
.#..#..#..
.#.###.#..
.#.....#..
..#####...
4 8
........
.##.....
.#......
........

예제 출력 1

1
0
1

출처

Contest > 아니메컵 > 아니메컵 1쿨 B번