정사각형 카펫

Frugal 씨가 새 집을 샀다. 그는 편안하게 쉴 수 있는 거실이 마음에 들어서 이 집이 정말 좋은 매물이라고 생각한다.

그런데 실망스럽게도 거실 바닥에 긁힌 자국이 몇 군데 있다.

바닥은 직사각형이고 정사각형 패널로 덮여 있다. 긁힌 패널을 모두 멀쩡한 패널로 바꾸고 싶지만 돈이 부족하다. 그래서 긁힌 패널을 카펫으로 덮기로 했다.

사용할 수 있는 카펫의 특징은 다음과 같다.

1. 카펫은 정사각형이다.
2. 카펫끼리 겹쳐도 된다.
3. 카펫은 접을 수 없다.
4. 크기가 다른 카펫이 있다. 카펫 한 변의 길이는 패널 한 변의 길이의 배수이다.

카펫은 긁힌 패널을 모두 덮어야 하며, 멀쩡한 패널은 하나도 덮으면 안 된다.

예를 들어 긁힌 패널이 그림 1과 같다면 최소 6장의 카펫이 필요하다.

그림 1: 카펫으로 덮은 예

입력은 여러 개의 데이터 셋으로 이루어진다. 입력의 끝은 0 0이 적힌 줄로 표시된다.

DataSet1
DataSet2
...
DataSetn
0 0

각 데이터 셋은 바닥의 상태를 나타내며 다음 형식으로 주어진다.

W H
P11 P12 P13 ... P1W
P21 P22 P23 ... P2W
...
PH1 PH2 PH3 ... PHW

W와 H는 거실의 x방향과 y방향 패널 개수를 나타내는 양의 정수이며, 둘 다 10 이하이다. $P_{yx}$는 y행 x열 패널의 상태이다. 0은 멀쩡한 패널(덮으면 안 됨), 1은 긁힌 패널(반드시 덮어야 함)을 뜻한다.

각 데이터 셋마다 긁힌 패널을 모두 덮는 데 필요한 카펫의 최소 개수를 한 줄에 출력한다.