У Максима есть калькулятор. В калькуляторе есть две целочисленные ячейки. Сначала в первой ячейке записано число 1, а во второй 0. За одно действие можно выполнить одну из описанных ниже операций:
- Пусть в текущий момент времени в первой ячейке записано число a, а во второй число b. Записать во вторую ячейку число b + 1;
- Пусть в текущий момент времени в первой ячейке записано число a, а во второй число b. Записать в первую ячейку число a·b.
Сейчас Максим интересуется следующей задачей: сколько существует целых чисел x (l ≤ x ≤ r) таких, что число x можно записать в первую ячейку калькулятора выполнив не более p действий.
Выходные данные
В единственную строку выведите целое число — ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 10 3
|
1
|
|
2
|
2 111 100
|
106
|
|
3
|
2 111 11
|
47
|