Два друга — Данил и Даниил — шли домой дорогой ночной, вдруг они придумали игру. Эта игра проходит следующим образом: На доске изначально написано число $$$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
| Name |
|---|


