Задача B. Хвостовые нули

Автор:А. Баранов, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:32 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

Выходной файл должен содержать единственное целое число — количество нулевых разрядов.

Ограничения

0 < A ≤ B < 264, 2 ≤ q < 232

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 100 10
24
2
9 75 120
17

0.036s 0.008s 15