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

输入格式

第一行包含一个整数 $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$)。

输出格式

对于第 $i$ 个测试用例，输出 $k_i$ —— 将 $w_i \times h_i$ 的矩形切割成 $k_i$ 个正方形所需的最小正方形数量。接下来的 $k_i$ 行，每行应包含三个整数：$x_{ij}, y_{ij}, l_{ij}$ —— 第 $j$ 个正方形左下角的坐标及其边长 ($0 \le x_{ij} \le w_i - l_{ij}$；$0 \le y_{ij} \le h_i - l_{ij}$)。矩形的左下角坐标为 $(0, 0)$，右上角坐标为 $(w_i, h_i)$。

样例

输入 1

3
5 3
5 6
4 4

输出 1

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

示例 1

示例 2

示例 3