Вам задано прямокутник, ширина якого w та висота h- натуральні числа. Прямокутник можна розрізати на два менші прямокутники прямим горизонтальним або прямим вертикальним розрізом у довільній цілочисельній позиції. Наприклад, одним з можливих способів розрізати прямокутник (5, 8) на дві частини буде розрізати його на (2, 8) і (3, 8). Інший спосіб розрізати його на дві частини - це (5, 4) і (5, 4) і т.д. Отримані менші частини можна розрізати ще на менші частини, якщо довжина сторони, що розрізається, принаймні дорівнює двом, щоб можна було розрізати. Забороняється різати кілька шматків одним рухом леза, складаючи шматки один на одного.

Ваше завдання - продовжувати розрізати заданий прямокутник на менші частини до тих пір, поки кожна частина не стане квадратом, тобто ширина кожної частини не буде дорівнювати її висоті. Це завжди можливо, оскільки можна просто продовжувати різати до тих пір, поки розмір кожного шматка не стане 1 на...