AT_arc226_c.Square Corner Packing

There is a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left. Initially, all cells are white.

You may perform the following operation any number of times.

• Choose integers $r,c,s$ satisfying all of the following conditions, and paint the cells $(r,c),(r+s,c),(r,c+s),(r+s,c+s)$ black.

  • $1\le r<r+s\le H$
  • $1\le c<c+s\le W$
  • The cells $(r,c),(r+s,c),(r,c+s),(r+s,c+s)$ are all white.

Find the maximum number of operations you can perform, and output one sequence of operations that achieves that maximum.

You are given $T$ test cases; solve each of them.

有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。初始时，所有格子均为白色。

你可以执行以下操作任意多次：

• 选择满足以下所有条件的整数 $r,c,s$，并将格子 $(r,c)$、$(r+s,c)$、$(r,c+s)$、$(r+s,c+s)$ 染成黑色：

  • $1\le r<r+s\le H$
  • $1\le c<c+s\le W$
  • 格子 $(r,c)$、$(r+s,c)$、$(r,c+s)$、$(r+s,c+s)$ 当前均为白色。

求最多能执行多少次该操作，并输出一个达到该最大次数的操作序列。

你将得到 $T$ 组测试数据；请对每组数据求解。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$H$ $W$

输入从标准输入给出，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例的格式如下：

$H$ $W$

For each test case, let $K$ be the maximum possible number of operations, and let $r_i,c_i,s_i$ be the integers chosen in the $i$-th operation; output them in the following format:

$K$
$r_1$ $c_1$ $s_1$
$r_2$ $c_2$ $s_2$
$\vdots$
$r_K$ $c_K$ $s_K$

If there are multiple sequences of operations that achieve the maximum, any of them will be accepted.

对于每个测试用例，设 $K$ 为可执行操作的最大次数，$r_i,c_i,s_i$ 为第 $i$ 次操作中选择的整数；请按以下格式输出：

$K$
$r_1$ $c_1$ $s_1$
$r_2$ $c_2$ $s_2$
$\vdots$
$r_K$ $c_K$ $s_K$

若存在多种操作序列均可达到最大次数，则输出其中任意一种即可。

Sample 1 Explanation:
For the first test case, performing the six output operations paints the following cells black. The digit $i$ represents a cell painted black by the $i$-th operation, and . represents a cell that is never painted.

There are other outputs that will be accepted.

Constraints

• $1\le T\le 500$
• $2\le H,W\le 500$
• The sum of $HW$ over all test cases is at most $250000$.
• All input values are integers.

样例 1 解释：
对于第一个测试用例，执行六次输出操作后，将以下格子涂成黑色。数字 $i$ 表示由第 $i$ 次操作涂黑的格子，. 表示从未被涂黑的格子。

存在其他可被接受的输出。

约束条件

• $1\le T\le 500$
• $2\le H,W\le 500$
• 所有测试用例中 $HW$ 的总和不超过 $250000$。
• 所有输入值均为整数。