13480번 - Hard Cuts 스페셜 저지다국어

Given a rectangle with integer side lengths, your task is to cut it into the smallest possible number of squares with integer side lengths.

The first line contains a single integer T — the number of test cases (1 ≤ T ≤ 3600). Each of the next T lines contains two integers w_i, h_i — the dimensions of the rectangle (1 ≤ w_i, h_i ≤ 60; for any i ≠ j, either w_i ≠ w_j or h_i ≠ h_j ).

For the i-th test case, output k_i — the minimal number of squares, such that it is possible to cut the w_i by h_i rectangle into k_i squares. The following k_i lines should contain three integers each: x_ij , y_ij — the coordinates of the bottom-left corner of the j-th square and l_ij — its side length (0 ≤ x_ij ≤ w_i − l_ij ; 0 ≤ y_ij ≤ h_i −l_ij ). The bottom-left corner of the rectangle has coordinates (0, 0) and the top-right corner has coordinates (w_i, h_i).

Example case 1

Example case 2

Example case 3