Иван – профессиональный строитель. Помимо тщательного контроля при строительстве он также следит за качеством материалов.

Иван решил сделать деревянный забор, поэтому он приобрёл доску длиной $$$L$$$ сантиметров. Однако для строительства забора необходимы доски длиной ровно $$$D$$$ сантиметров. Разумеется доску можно распилить на несколько частей, но из-за сжатых сроков Иван успеет распилить её не более, чем на $$$K$$$ частей.

Ему стало интересно, какое максимальное количество досок длины $$$D$$$ ему удастся получить? Напишите программу, которая по числам $$$L$$$, $$$D$$$, $$$K$$$ вычисляет это количество.

Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему.

Федя совсем недавно поступил в лучший вуз страны. В особенности ему стала интересна кафедра изучения счастливых чисел, то есть тех чисел, которые состоят только из цифр 2 и 5. Научные сотрудники этой кафедры исследуют их распределение. Они поняли, что существует последовательность всех счастливых чисел в порядке возрастания (2 - первое число, 5 - второе, 22 - третье и т.д.). Они хотят найти порядковый номер счастливого числа $$$N$$$ в данной последовательности. Федю очень заинтересовала эта задача. Он думал над ней целый день, но так ни к чему и не пришел. Можете ли вы помочь Феде и кафедре счастливых чисел найти ответ?

Сегодня знаменательный день! В Межгалактическом Обществе Программистов сразу у $$$n$$$ программистов день рождения! Поскольку программисты в этом обществе – очень дружный народ, они решили отпраздновать эти дни рождения все вместе.

Как известно, все разумные существа во вселенной в день рождения зажигают свечки на торте. Программисты зажигают свечки в соответствии с двоичной записью числа. Например, если программисту исполнилось $$$24$$$ года, он втыкает в торт $$$5$$$ свечек и зажигает только первые $$$2$$$, поскольку $$$24_{10} = 11000_2$$$, a если ему исполнилось $$$31$$$, то придется зажечь все $$$5$$$ свечек.

Программисты быстро заметили, что если свечка не была зажжена то ее можно вытащить из торта и воткнуть в следующий. Конечно, они не хотят расходовать лишних свечек и поэтому решили посчитать, в каком порядке стоит праздновать дни рождения, чтобы минимизировать их расход.

Поскольку общество межгалактическое, в нем есть индивиды самого разного возраста от $$$1$$$ до $$$10^9$$$ лет.

Напишите программу, которая определяет наименьшее количество свечек, которое потребуется, чтобы отпраздновать все дни рождения.

Гарантируется, что решение, работающее, когда числа уже даны в правильном порядке наберет не менее $$$10$$$ баллов.

Гарантируется, что решение, работающее, когда все числа имеют одинаковую длину в двоичной записи наберет не менее $$$30$$$ баллов.

Сегодня Егор в школе проходил системы счисления, ему дали следующее определение представление числа в системе счисления:

Представлением целого положительного числа $$$n$$$ в $$$k$$$-ичной системе счисления ($$$k \ge 2$$$) называется последовательность целых неотрицательных чисел $$$a_1$$$, ..., $$$a_s$$$ такая, что $$$a_i \le k - 1$$$ для всех $$$i = 1...s$$$ и $$$a_1 \ne 0$$$, а также $$$a_s + a_{s - 1} \cdot k + a_{s - 2} \cdot k^2 + ... + a_1 \cdot k^{s - 1} = n$$$.

Например, представлением числа 6 в двоичной системе счисления является последовательность $$$1, 1, 0$$$, т.к. $$$0 + 1 \cdot 2 + 1 \cdot 4 = 6$$$, а представлением числа 120 в одиннадцатиричной системе счисления является последовательность $$$10, 10$$$, т.к. $$$10 + 10 \cdot 11 = 120$$$.

Можно показать, что любое целое положительное число $$$n$$$ представимо единственным образом в $$$k$$$-ичной системе счисления для любого $$$k \ge 2$$$.

Егор считает красивыми последовательности, которые заканчиваются ровно на два нуля. Сегодня в учебнике он наткнулся на целое положительное число $$$n$$$, и он захотел получить из него как можно больше красивых последовательностей, переводя $$$n$$$ в различные системы счисления. Ему стало интересно, сколько различных красивых последовательностей он сможет получить?

Однако, так как число $$$n$$$ очень большое, без программирования ему не обойтись. К сожалению, программировать он не умеет, поэтому обратился за помощью к вам. Напишите программу, которая по заданному $$$n$$$ считает количество различных красивых последовательностей, которые из него можно получить.

Решения, работающие корректно при $$$n \le 10^6$$$, будут оцениваться в 30 баллов.

Решения, работающие корректно при $$$n \le 10^{12}$$$, будут оцениваться в 60 баллов.