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.
Input
The first line contains a single integer t (1 ≤ t ≤ 3600) - the number of test cases. 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]).
Output
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]).
