P7038 [NWRRC 2016] 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 \le T \le 3600)$ . Each of the $next T$ lines contains two integers $w_{i}, h_{i}$ -- the dimensions of the rectangle $(1 \le w_{i}, h_{i} \le 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 \le x_{ij} \le w_{i} − l_{ij} ; 0 \le y_{ij} \le 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}).$

Time limit: 2 s, Memory limit: 256 MB.