Плитка для пола
Вы хотите украсить пол квадратной плиткой. Вам нравятся прямоугольники. Из шести квадратных плиток можно составить ровно два уникальных прямоугольника, используя все плитки: 1×6 и 2×3 (6×1 считается тем же, что и 1×6. Аналогично, 3×2 то же самое, что и 2×3). Также из четырех квадратных плиток можно составить ровно два уникальных прямоугольника: 1×4 и 2×2.
Дано целое число N. Какое минимальное количество квадратных плиток необходимо, чтобы можно было составить ровно N уникальных прямоугольников, используя все плитки? Если N=2, ответ 4.
Входные данные
Входные данные содержат несколько тестов. Каждый тест состоит из одной строки с одним целым числом N (1 ≤ N ≤ 75), которое обозначает количество желаемых прямоугольников. Входные данные заканчиваются строкой, содержащей число 0.
Выходные данные
Для каждого теста выведите одно целое число в отдельной строке, представляющее минимальное количество квадратных плиток, необходимых для формирования ровно N прямоугольников, используя все плитки. Гарантируется, что ответ не превышает 10^18. Не выводите лишние пробелы и не разделяйте ответы пустыми строками.