В той самой вселенной, где в Уфе появится метро, за постройку метро назначили Ик Билина. Естественно, он хочет сделать это по своему.
Сначала он выбирает число $$$n$$$ и строит первый и самый большой круг метро из $$$n$$$ станций. Дальше он будет строить круговые линии метро, пока это возможно (число делится без остатка) по его формуле $$$a_i = \frac{a_{i - 1}}{i}$$$, где $$$i$$$ — номер круга метро (начинается с 1) и $$$a_i$$$ — количество станций на $$$i$$$-м круге.
Флюр все продумал и понял, что самый последний круг метро должен иметь ровно $$$p$$$ станций, но не продумал, сколько станций должно быть в первом круге метро. К сожалению, он не силен в геометрических прогрессиях и он просит вас узнать, сколько чисел от $$$l$$$ до $$$r$$$ подходит в качестве числа $$$n$$$ (количество станций в первом круге метро) в соответствии с его условием (последний возможный круг равен $$$p$$$).
В первой и единственной строке ввода даны числа $$$l$$$, $$$r$$$ $$$(1 \le l \le r\le 10^{18})$$$ и $$$p$$$ $$$(1 \le p \le 10^{18})$$$.
Выведите ответ на просьбу Ик Билина
Всего в задаче $$$25$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 4 балла.
2 18 3
2
В примере подходят 2 числа: 3 и 18.
Первый круг равен 3. 3 не делится на 2, значит первый и последний круг равен 3.
Первый круг равен 18. Второй круг 18 / 2 = 9. Третий круг 9 / 3 = 3. Последний круг равен 3, т.к. 3 не делится на 4.
