D. Box
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Little-L has a box divided into an $$$n \times m$$$ grid of cells.

Initially, all cells are empty. You can perform several operations, each of which can be one of the following two types:

  1. Choose a cell and place a small ball in every empty cell in the same row and the same column as the chosen cell.
  2. Choose a cell and place a small ball in every empty cell on the two diagonals passing through the chosen cell.

For example, in a $$$5 \times 5$$$ box, choosing cell $$$(3,4)$$$ for either the first or the second operation would yield the following results:

The left figure shows the first operation, and the right figure shows the second operation.

Little-L wants to know: what is the minimum number of operations needed to fill all cells in the box with balls?

Note: You can perform an operation on a cell that already contains a ball.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^3$$$), representing the number of rows and columns of the box.

In each test file, it is guaranteed that the sum of $$$n \times m$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case:

The first line should contain a single integer $$$p$$$ ($$$1 \leq p \leq n \times m$$$), representing the minimum number of operations.

The next $$$p$$$ lines each contain three integers $$$op, x, y$$$ ($$$op \in \{1,2\}, 1 \leq x \leq n, 1 \leq y \leq m$$$), indicating one operation. If $$$op=1$$$, perform the first type of operation at cell $$$(x,y)$$$; if $$$op=2$$$, perform the second type of operation at cell $$$(x,y)$$$.

Example
Input
2
3 4
2 2
Output
3
2 2 2
2 2 3
1 2 4
2
1 1 1
1 2 2