Сегодня на уроке информатики в школе Насти рассказывали про НОД (GCD) и НОК (LCM) (см. ссылки ниже). Так как Настя очень умная, то она быстро сделала все задания, и теперь предлагает вам тоже решить одно из них.
Назовем пару целых чисел (a, b) хорошей, если GCD(a, b) = x и LCM(a, b) = y, где GCD(a, b) обозначает наибольший общий делитель чисел a и b, а LCM(a, b) обозначает наименьшее общее кратное чисел a и b.
Вам даются целые числа x и y. Требуется узнать количество хороших пар целых чисел (a, b) таких, что l ≤ a, b ≤ r. Заметьте, что пары (a, b) и (b, a) считаются различными, если a ≠ b.
Выходные данные
В первой строке выведите единственное число — ответ на задачу.
Примечание
В первом тесте есть две подходящих хороших пары чисел (a, b) — (1, 2) и (2, 1).
Во втором тесте есть четыре подходящих хороших пары чисел (a, b) — (1, 12), (12, 1), (3, 4), (4, 3).
В третьем тесте есть хорошие пары чисел, к примеру, (3, 30), но ни одна из них не удовлетворяет ограничению l ≤ a, b ≤ r.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2 1 2
|
2
|
|
2
|
1 12 1 12
|
4
|
|
3
|
50 100 3 30
|
0
|