종이 지도

상근이의 농장은 너무 넓어서 어느 자리에 어떤 식물을 심었는지 따로 기록해 둬야 한다. 상근이는 기록을 남기려고 인터넷 쇼핑몰에서 고화질 지도를 주문했다. 지도가 워낙 커서 종이 한 장에 다 인쇄할 수는 없으니, 지도를 나눠 여러 장에 인쇄해야 한다.

같은 지도라도 종이를 어떻게 올려놓느냐에 따라 필요한 장수가 달라진다. 예를 들어 텍사스처럼 생긴 지도는 배치를 잘못 잡으면 종이 14장이 들지만, 같은 크기의 종이라도 잘 맞추면 10장이면 된다.

종이의 변은 모두 x축과 y축에 평행해야 한다. 종이는 회전시킬 수 없고, 두 종이는 한 변 전체를 맞댈 때만 서로 접할 수 있다. 그래서 종이는 하나의 규칙적인 격자를 따라 놓이고, 정할 수 있는 것은 그 격자를 가로세로로 얼마나 밀지뿐이다. 격자 칸 중에서 'X'가 하나라도 들어 있는 칸만 실제로 인쇄한다.

지도와 종이의 크기가 주어질 때, 지도를 인쇄하는 데 필요한 종이 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있고, 입력이 끝날 때까지 계속된다.

각 테스트 케이스의 첫째 줄에 네 정수 $A_r$, $A_c$, $T_r$, $T_c$가 주어진다. $A_r$과 $A_c$는 지도의 세로와 가로 픽셀 개수이고, $T_r$과 $T_c$는 종이 한 장에 인쇄할 수 있는 세로와 가로 픽셀 개수이다. ($1 \le A_r, A_c \le 1000$, $1 \le T_r, T_c \le 100$)

다음 $A_r$개 줄에는 각각 $A_c$개의 문자가 공백 없이 주어진다. 'X'는 상근이의 농장이고, '.'는 농장이 아닌 곳이다.

모든 'X'를 인쇄해야 하며, 지도의 'X'는 모두 하나의 영역으로 이어져 있다.

각 테스트 케이스마다 모든 'X'를 인쇄하는 데 필요한 종이 개수의 최솟값을 한 줄에 하나씩 출력한다.