There is a grid with $n$ columns and $m$ rows, with the top-left corner at $(0, 0)$ and the bottom-right corner at $(n, m)$. You are to cover all edges using two types of L-shaped tiles. Each edge must be covered exactly once by one L-shaped tile. You must output a valid covering scheme and use the minimum possible number of L-shaped tiles. The two types of L-shaped tiles consist of two segments of length $1+1$ and two segments of length $1+2$ (see Figure 1 for detailed shapes).

Input

The input is read from the file cover.in. The first line contains an integer $T$, representing the number of test cases. The next $T$ lines each contain two integers $n, m$, representing the grid size.

Output

The output is written to the file cover.out. For each test case, the first line should output the number of L-shaped tiles used, $k$. The next $k$ lines each output one L-shaped tile. An L-shaped tile is represented by three integers $x, y, t$, where $x, y$ represent the intersection point of the two segments of the L-shaped tile, and $t$ represents the ID of the L-shaped tile. See Figure 1 for details. The blue numbers indicate the ID of the L-shaped tile above the number.

Figure 1: Each type of L-shaped tile and its ID

Examples

Input 1

2
2 2
2 3

Output 1

4
2 2 8
1 2 8
0 1 1
0 0 1
6
1 3 6
0 2 1
2 3 8
2 1 7
1 0 2
0 0 2

Note

The covering scheme for the first test case in the example is shown in Figure 2. It uses 4 L-shaped tiles.

Figure 2: Covering scheme for the first test case

The covering scheme for the second test case in the example is shown in Figure 3. It uses 6 L-shaped tiles.

Figure 3: Covering scheme for the second test case

Constraints

For all test data, it is guaranteed that $1 \le n \times m \le 10^5$ and $\sum n \times m \le 5 \times 10^5$.

Subtasks

This problem has partial scoring. For all data in a test case, if the output scheme is valid and uses the minimum number of L-shaped tiles, you will receive 100% of the points for that test case. If the output scheme is valid but some data does not use the minimum number of L-shaped tiles, you will receive 20% of the points for that test case. If the output scheme is invalid, you will receive 0 points for that test case.

Implementation Details

In the contestant's directory, cover/check.cpp can be used to check if your output is correct and to output the number of L-shaped tiles used. You can use the following command to compile the checker:

g++ -std=c++14 -O2 -o check check.cpp

Use the following command in Linux to check your output:

./check <input-file> <output-file>

Or use the following command in Windows to check your output:

check.exe <input-file> <output-file>

Where <output-file> is your output and <input-file> is the input corresponding to your output. The program will output a check log to standard output, with one line of log for each test case in the input. The logs have three levels:

• CRITICAL: Indicates that the checker encountered an unrecoverable error, such as incorrect runtime arguments or failure to open input/output files. After outputting this type of log, the checker will stop immediately.
• ERROR: Indicates that the output covering scheme is invalid. The checker will output the reason for the error, but this will not terminate the checker.
• INFO: Indicates that the output covering scheme is valid. The checker will also output the number of L-shaped tiles used.