Description

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

Input Format

第一行包含一个整数 $T$ —— 测试用例的数量 $(1 \le T \le 3600)$。接下来的 $T$ 行中的每一行包含两个整数 $w_{i}, h_{i}$ —— 矩形的尺寸 $(1 \le w_{i}, h_{i} \le 60$；对于任何 $i \neq j$，要么 $w_{i} \neq w_{j}$，要么 $h_{i} \neq h_{j})$。

Output Format

对于第 $i$ 个测试用例，输出 $k_{i}$ —— 最小的正方形数量，使得可以将 $w_{i}$ 乘以 $h_{i}$ 的矩形切割成 $k_{i}$ 个正方形。接下来的 $k_{i}$ 行应包含三个整数：$x_{ij}, y_{ij}$ —— 第 $j$ 个正方形左下角的坐标，以及 $l_{ij}$ —— 其边长 $(0 \le x_{ij} \le w_{i} - l_{ij}; 0 \le y_{ij} \le h_{i} - l_{ij})$。矩形的左下角坐标为 $(0, 0)$，右上角坐标为 $(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

Hint

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。