시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB519821.622%

## 문제

Given a rectangle with integer side lengths, your task is to cut it into the smallest possible number of squares with integer side lengths.

## 입력

The first line contains a single integer T — the number of test cases (1 ≤ T ≤ 3600). Each of the next T lines contains two integers wi, hi — the dimensions of the rectangle (1 ≤ wi, hi ≤ 60; for any i ≠ j, either wi ≠ wj or hi ≠ hj ).

## 출력

For the i-th test case, output ki — the minimal number of squares, such that it is possible to cut the wi by hi rectangle into ki squares. The following ki lines should contain three integers each: xij , yij — the coordinates of the bottom-left corner of the j-th square and lij — its side length (0 ≤ xij ≤ wi − lij ; 0 ≤ yij ≤ hi −lij ). The bottom-left corner of the rectangle has coordinates (0, 0) and the top-right corner has coordinates (wi, hi).

## 예제 입력 1

3
5 3
5 6
4 4


## 예제 출력 1

4
0 0 3
3 0 2
3 2 1
4 2 1
5
0 0 2
0 2 2
0 4 2
2 0 3
2 3 3
1
0 0 4


Example case 1

Example case 2

Example case 3