가장 적은 정사각형으로 자르기

변의 길이가 모두 정수인 직사각형을 변의 길이가 정수인 정사각형으로 자른다. 정사각형끼리는 겹치지 않고, 모두 합치면 직사각형을 빈틈없이 덮으며, 각 변은 직사각형의 변과 평행하다.

이렇게 자를 때 필요한 정사각형의 최소 개수를 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 625$).

다음 $T$개의 줄에는 각 테스트 케이스의 직사각형 두 변의 길이 $w_i$와 $h_i$가 공백으로 구분되어 주어진다 ($1 \le w_i, h_i \le 25$).

서로 다른 두 테스트 케이스의 변 길이 쌍은 같지 않다. 즉 $i \ne j$이면 $w_i \ne w_j$ 또는 $h_i \ne h_j$이다.

각 테스트 케이스마다 $w_i \times h_i$ 직사각형을 자르는 데 필요한 정사각형의 최소 개수를 입력 순서대로 한 줄에 하나씩 출력한다. 자르는 방법 자체는 출력하지 않는다.

$5 \times 3$ 직사각형은 한 변이 3, 2, 1, 1인 정사각형으로 나뉘므로 4개면 된다.

$5 \times 6$ 직사각형은 한 변이 2인 정사각형 3개와 한 변이 3인 정사각형 2개로 나뉜다. 한 변이 5인 정사각형을 먼저 잘라내면 $5 \times 1$ 띠가 남아 모두 6개가 되므로, 가장 큰 정사각형부터 잘라내는 방법이 늘 최선은 아니다.

$4 \times 4$ 직사각형은 그 자체가 정사각형이다.