Trailing Loves (or L'oeufs?)

Aki is fond of numbers, especially those with trailing zeros. For example, the number $9200$ has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers $n$ and $b$ (in decimal notation), your task is to calculate the number of trailing zero digits in the $b$ -ary (in the base/radix of $b$ ) representation of $n!$ (factorial of $n$ ).

Input

The only line of the input contains two integers $n$ and $b$ ( $1 \leq n \leq 10^{18}$ ).

Output

Print an only integer the number of trailing zero digits in the $b$ -ary representation of $n!$

Examples

Input

6 9

Output

Input

38 11

Output

Input

5 2

Output

Input

Copy

5 10

Output

1

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {

long long n, b;

cin >> n >> b;

long long ans = 0;

long long i = 1;

while (b * i <= n) {

ans++;

i++;

}

cout << ans + 1 << endl;

return 0;

}

Comments