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 w_i, h_i — the dimensions of the rectangle (1 ≤ w_i, h_i ≤ 60; for any i ≠ j, either w_i ≠ w_j or h_i ≠ h_j ).

출력 형식

For the i-th test case, output k_i — the minimal number of squares, such that it is possible to cut the w_i by h_i rectangle into k_i squares. The following k_i lines should contain three integers each: x_ij , y_ij — the coordinates of the bottom-left corner of the j-th square and l_ij — its side length (0 ≤ x_ij ≤ w_i − l_ij ; 0 ≤ y_ij ≤ 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).

예제 입력

3
5 3
5 6
4 4

예제 출력

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

힌트

</p>

Example case 1

Example case 2

Example case 3