Hard Cuts

You are given a rectangle whose side lengths are integers. Cut it into squares whose side lengths are also integers. The squares do not overlap, together they cover the whole rectangle with no gap, and every side of every square is parallel to a side of the rectangle.

Find the smallest number of squares such a cut can use.

The first line contains the number of test cases $T$ ($1 \le T \le 625$).

Each of the next $T$ lines contains two integers $w_i$ and $h_i$, the side lengths of one rectangle ($1 \le w_i, h_i \le 25$).

No two test cases have the same pair of side lengths. That is, if $i \ne j$, then $w_i \ne w_j$ or $h_i \ne h_j$.

For each test case, print the minimum number of squares needed to cut the $w_i \times h_i$ rectangle. Print one number per line, in the order the test cases are given. Do not print the cut itself.

A $5 \times 3$ rectangle splits into squares of side 3, 2, 1 and 1, so 4 squares are enough.

A $5 \times 6$ rectangle splits into three squares of side 2 and two squares of side 3. Cutting off a square of side 5 first leaves a $5 \times 1$ strip and costs 6 squares, so taking the largest square first is not always best.

A $4 \times 4$ rectangle is already a square.