Сегодня компания Interplanetary Software Inc. решила провести опыт по изучению марсианских чисел.
У вас есть число $$$a$$$. Пара чисел $$$(x; y)$$$ является марсианской, если наибольший общий делитель этих двух чисел равен 1.
Компания решила исследовать все числа на отрезке $$$[l; r]$$$ и определить, сколько чисел из отрезка образуют марсианскую пару с числом $$$a$$$.
В первой строке вам даются три числа: $$$a$$$, $$$l$$$, $$$r$$$ $$$(1 \le a \le 10^7)$$$, $$$(1 \le l \le r \le 10^{18})$$$ — число для проверки и границы отрезка.
Выведите единственное число — количество чисел, образующих марсианскую пару с $$$a$$$ на отрезке $$$[l; r]$$$.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| $$$1$$$ | $$$50$$$ | тесты из условия | – | полная |
| $$$2$$$ | $$$100$$$ | $$$a, l, r \le 10^6$$$ | 1 | первая ошибка |
| $$$3$$$ | $$$100$$$ | $$$l, r \le 2 \cdot 10^7$$$ | 1-2 | первая ошибка |
| $$$4$$$ | $$$100$$$ | $$$r - l \le 10^6$$$ | 1 | первая ошибка |
| $$$5$$$ | $$$150$$$ | $$$r - l \le 2 \cdot 10^7$$$ | 1, 4 | первая ошибка |
| $$$6$$$ | $$$250$$$ | нет | 1-5 | первая ошибка |
5 4 8
4
3 1 20
14
