题目描述

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}).$

题目大意

题目描述

给定一个边长为整数的矩形，您的任务是将其切割成边长为整数的正方形的尽可能少的正方形。

3
5 3
5 6
4 4

4
0 0 3
3 0 2
3 2 1
4 2 1
5
0 0 2
0 2 2
0 4 2
2 0 3
2 3 3
1
0 0 4

提示

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