이상한 광고판

재구성이 가능한 광고판은 R x C 크기의 정사각형 타일을 격자 모양으로 배치한 것입니다. 각 타일은 한쪽 면이 흰색, 반대쪽 면이 검은색입니다.

막대기로 타일을 두드려 그림을 바꿉니다. 타일을 두드리면 그 타일이 뒤집혀 반대쪽 면이 보입니다(흰색은 검은색으로, 검은색은 흰색으로 바뀝니다). 타일들이 빈틈없이 맞붙어 있어 옆면이 서로 닿아 있기 때문에, 한 타일을 두드리면 그 타일과 한 변 전체를 맞대고 있는 모든 타일, 즉 바로 위, 아래, 왼쪽, 오른쪽 타일도 함께 뒤집힙니다. 따라서 내부에 있는 타일을 두드리면 자기 자신과 이웃 4개를 합쳐 한 번에 5개의 타일이 뒤집히고, 가장자리나 모서리의 타일은 이웃이 적어 더 적은 수의 타일이 뒤집힙니다.

처음 배열이 주어졌을 때, 모든 타일을 흰색 면으로 만들기 위해 필요한 최소 두드림 횟수를 구하세요. 어떤 배열은 결코 모두 흰색으로 만들 수 없습니다.

입력에는 여러 개의 광고판 정보가 들어 있습니다. 각 정보는 두 정수 R과 C(1 <= R, C <= 16), 즉 행과 열의 수가 적힌 줄로 시작합니다. 이어지는 R개의 줄에는 각각 정확히 C개의 문자가 있습니다. 대문자 X는 검은색 타일, 마침표 .는 흰색 타일을 뜻합니다. 각 광고판 뒤에는 빈 줄이 하나 옵니다.

입력은 광고판 크기 대신 두 개의 0(0 0)이 적힌 줄로 끝납니다. 이 종료 표시는 광고판이 아니며 출력하지 않습니다.

각 광고판마다 정확히 한 줄을 출력합니다.

• 모두 흰색으로 만들 수 있으면 You have to tap T tiles.를 출력합니다. 여기서 T는 필요한 최소 두드림 횟수입니다. 문장 형식은 고정되어 있어, T가 0이나 1일 때에도 항상 tiles라는 단어를 그대로 사용합니다.
• 모든 타일을 흰색으로 만드는 것이 불가능하면 대신 Damaged billboard.를 출력합니다.