치노의 라떼 아트 (Easy)
면접 대비시간 제한1초메모리 제한1024 MB
격자에 채워진 크림이 N×N 정사각형에서 모서리 하나의 M×M 정사각형을 뺀 하트 모양인지 판별합니다.
문제
치노는 하트 모양의 라떼 아트를 만드는 연습을 하고 있다. 치노가 연습하며 남긴 흔적을 우연히 본 코코아는 그중 하트 모양의 라떼 아트가 몇 개인지 궁금해졌다. 코코아를 위해 라떼 위 크림이 하트 모양인지 판별하는 프로그램을 만들어 보자.
하트 모양
이 문제에서 치노의 라떼 아트는 단위 정사각형으로 나뉜 2차원 격자로 주어진다. #는 크림으로 꽉 찬 정사각형, .는 크림이 없는 정사각형을 나타낸다.
두 양의 정수 과 ()이 존재해서, 정사각형의 네 구석 중 한 곳에서 정사각형을 제거한 모양을 하트 모양으로 정의한다.
다음은 , 인 경우의 하트 예시이다.
###..
###..
#####
#####
#####
위 정의에 해당하는 모양의 크림이 라떼 위에 정확히 하나만 놓여 있는 경우에만 하트로 인정한다. 크림 안에 구멍이 뚫려 있거나, 떨어진 크림 덩어리가 여러 개인 경우(각 덩어리가 하트 모양인 경우도 포함)는 하트 모양으로 보지 않는다.
입력
첫 번째 줄에 테스트 케이스의 개수 가 주어진다. ()
다음 줄부터 개의 테스트 케이스가 아래 형식으로 주어진다.
각 테스트 케이스의 첫 줄에 격자의 세로 길이 과 가로 길이 가 공백으로 구분되어 주어진다. ()
이어서 개의 줄에 격자의 행을 나타내는 길이 의 문자열이 주어진다. 각 문자열은 # 또는 .로만 이루어진다.
출력
각 테스트 케이스에 대해, 주어진 라떼 아트가 하트 모양이면 1, 아니면 0을 한 줄에 하나씩 출력한다.