Statement is not available in English language
F. Double D
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два друга — Данил и Даниил — шли домой дорогой ночной, вдруг они придумали игру. Эта игра проходит следующим образом: На доске изначально написано число $$$n$$$. У Данила есть число $$$d_1$$$, а у Даниила — число $$$d_2$$$. Игра состоит из нескольких ходов. Данил и Даниил ходят по очереди. Первым ходит игрок с меньшим количеством букв «и» в своём имени (Данил). На каждом ходу игрок, которому принадлежит ход, пытается разделить число, написанное на доске (обозначим его $$$x$$$), на своё число. Если $$$x$$$ делится на число игрока нацело, то число на доске заменяется на результат деления, иначе вместо $$$x$$$ записывается $$$x - 1$$$. Затем ход завершается, а очередь ходить переходит к другому игроку. Как только $$$x$$$ становится равным нулю, игра завершается. Данилу и Даниилу интересно, сколько ходов произойдёт в такой игре в зависимости от значений $$$n$$$, $$$d_1$$$ и $$$d_2$$$.

Входные данные

Единственная строка содержит три натуральных числа, $$$n$$$, $$$d_1$$$, $$$d_2$$$ $$$(2 \le n, d_1, d_2 \le 10^{18})$$$.

Выходные данные

Выведите одно число — количество ходов, которое сделают игроки.

Система оценки
ГруппаБаллыДоп. ограниченияНеобх. группыКомментарий
$$$0$$$$$$0$$$Тесты из условия
$$$1$$$$$$40$$$$$$n, d_1, d_2 \leq 10^6$$$Каждый тест
$$$2$$$$$$60$$$Каждый тест
Примеры
Входные данные
15 2 3
Выходные данные
7
Входные данные
18 2 3
Выходные данные
5
Входные данные
5 6 7
Выходные данные
5
Примечание

Пояснение к примеру из условия:

1. Данил вычитает 1, число равно 14

2. Даниил вычитает 1, число равно 13

3. Данил вычитает 1, число равно 12

4. Даниил делит на 3, число равно 4

5. Данил делит на 2, число равно 2

6. Даниил вычитает 1, число равно 1

7. Данил вычитает 1, число равно 0