Марсианский друг

시간 제한2초메모리 제한1024 MB

요약

N!을 k진법으로 썼을 때 끝에 붙는 0의 개수를 구한다. N은 1e18, k는 1e9까지 주어진다.

난이도: 보통10점 중 5점
유형: 정수론, 수학
정답자: 아직 제출이 없습니다

문제

Десятиклассник Вася дружит с марсианином Хрулем. И сегодня Хруль попросил Васю помочь решить следующая задачу: необходимо найти на какое количество нулей заканчивается число $N!$ . Вася сначала обрадовался, ведь он решал такую задачу в пятом классе на олимпиадном кружке по математике. Но вовремя вспомнил, что на Марсе $k$ -ичная система счисления, и задумался.

Помогите Васе посчитать количество нулей в записи число $N!$ в $k$ -ичной системе счисления.

입력

Входной файл содержит два целых числа $N$ ( $1 \le N \le 10^{18}$ ) и $k$ ( $2 \le k \le 10^9$ ).

출력

В выходной файл выведите одно целое число --- ответ на задачу.

예제1

예제 1
입력
```
20 7
```
예상 출력
```
2
```