eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Трудные разрезы

Трудные разрезы

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Задан прямоугольник с целыми длинами сторон. Ваша задача - разрезать его на минимально возможное количество квадратов с целыми длинами сторон.

Вхідні дані

В первой строке записано одно целое число t (1t3600) - количество тестов. Каждая из следующих t строк содержит два целых числа w[i], h[i] - размеры прямоугольника (1w[i], h[i]60, для любого ij, либо w[i]w[j] либо h[i]h[j])

Вихідні дані

Для i - го теста выведите k[i] - минимальное количество квадратов, на которое можно разрезать прямоугольник w[i] на h[i] на k[i] квадратов. Следующие k[i] строк должны содержать по три целых числа в каждой: x[ij], y[ij] - координаты нижнего левого угла j-го квадрата и l[ij] - длина его стороны (0x[ij]w[i] - l[ij], 0y[ij]h[i] - l[ij]). Левый нижний угол прямоугольника имеет координаты (0, 0), а правый верхний угол имеет координаты (w[i], h[i]).

prb9440.gif

Приклад

Вхідні дані #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 3
0 3 3
3 0 2
3 2 2
3 4 2
1
0 0 4
Джерело 2016 ACM NEERC, Северный регион, Октябрь 22, Задача H