당신에게 RC개의 라이트 패널로 이루어진 크기 RxC의 직사각형 모양의 판자가 주어진다. i번째 줄의 j번째 문자는 i번째 행과 j번째 열에 있는 패널을 가리킨다. i번째 줄의 j번째 문자가 ‘*’ 이면 그 패널이 켜져 있다는 뜻이고 ‘.’이면 꺼져있다는 뜻이다.

당신이 어떤 패널을 터치했을 때 그 패널의 상태는 바뀐다. 즉 켜져 있으면 꺼지고 꺼져있으면 켜진다. 그런데 그 패널을 터치하면 8 방향으로 인접한 패널의 상태도 모두 바뀌게 된다.

당신은 모든 패널을 켜고 싶다. 최소 몇 번을 터치해야 모든 패널을 켤 수 있는지 구하는 게 문제이다.

입력

• 첫 번째 줄에는 판자의 크기를 나타내는 정수 R과 C가 공백을 사이로 주어진다. (1<=R,C<=8)
• 다음 R줄에는 각각 길이 C인 문자열이 주어진다. i번째 줄에 j번째 문자가 ‘*’ 이면 그 패널은 켜져 있다는 뜻이고 ‘.’이면 꺼져있다는 뜻이다.

출력

입출력 예

입력

5 5
*****
*...*
*...*
*...*
*****

출력 

1

입출력 예 보충

출처:topcoder
추천:likepad

//hint//