Задача D. Нули в окончании числа ≡

Условие

Обозначим за P(A, B) результат произведения всех натуральных чисел от A до B включительно.

Для заданных значений A, B и q требуется определить количество нулевых разрядов, которыми оканчивается q-ичная запись числа P(A, B).

Формат входного файла

Входной файл "input.txt" содержит три натуральных числа: A, B и q.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно единственное число, указывающее количество нулевых разрядов.

Ограничения

0 < A ≤ B < 2⁶⁴, 2 ≤ q < 2³²

Примеры тестов

1 100 10

24

9 75 120

17