Problem Statement

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.

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.

Input

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

Output

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.