Hard Cuts — Eolymp

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 3600$ 1 \leq t \leq 3600) - the number of test cases. Each of the next $t$ lines contains two integers $w_{i}$ w_i, $h_{i}$ h_i - the dimensions of the rectangle ( $1 \leq w_{i}, h_{i} \leq 60$ 1 \leq w_i, h_i \leq 60, for any $i \neq = j$ i \neq j, either $w_{i} \neq = w_{j}$ w_i \neq w_j or $h_{i} \neq = h_{j}$ h_i \neq h_j).

Output

For the $i$ -th test case, output $k_{i}$ k_i - the minimal number of squares into which it is possible to cut the $w_{i}$ w_i by $h_{i}$ h_i rectangle. The following $k_{i}$ k_i lines should contain three integers each: $x_{ij}$ x_{ij}, $y_{ij}$ y_{ij} - the coordinates of the bottom-left corner of the $j$ -th square and $l_{ij}$ l_{ij} - its side length ( $0 \leq x_{ij} \leq w_{i} - l_{ij}$ 0 \leq x_{ij} \leq w_i - l_{ij}, $0 \leq y_{ij} \leq h_{i} - l_{ij}$ 0 \leq y_{ij} \leq h_i - l_{ij}). The bottom-left corner of the rectangle has coordinates $(0, 0)$ and the top-right corner has coordinates $(w_{i}, h_{i})$ (w_i, h_i).

Examples

Example 1

Loading