#include<fstream>
using namespace std;
ifstream fin("pascal.in");
ofstream fout("pascal.out");
long long r,d,p,sol,P,Q;
int main()
{
    long long i;
    fin>>r>>d;
    if (d==2 || d==3 || d==5)
    {
        for (long long i=d;i<=r;i*=d)
            P+=r/i;
        for (i=1;i<(r>>1);++i)
        {
            long long nr=0;
            for (long long j=d;j<=i;j*=d)
                nr+=i/j;
            for (long long j=d;j<=r-i;j*=d)
                nr+=(r-i)/j;
            if (P>nr) ++sol;
        }
        sol<<=1;
        long long nr=0;
        for (long long j=d;j<=r/2;j*=d)
            nr+=r/2/j;
        for (long long j=d;j<=r-r/2;j*=d)
            nr+=(r-r/2)/j;
        if (P>nr)
        {
            if (r&1) ++++sol;
            else ++sol;
        }
    }
    if (d==4)
    {
        for (long long i=2;i<=r;i<<=1)
            P+=r/i;
        for (i=1;i<(r>>1);++i)
        {
            long long nr=0;
            for (long long j=2;j<=i;j<<=1)
                nr+=i/j;
            for (long long j=2;j<=r-i;j<<=1)
                nr+=(r-i)/j;

            if (P>nr+1) ++sol;
        }
        sol<<=1;
        long long nr=0;
        for (long long j=2;j<=r/2;j<<=1)
            nr+=r/2/j;
        for (long long j=2;j<=r-r/2;j<<=1)
            nr+=(r-r/2)/j;
        if (P>nr+1)
        {
            if (r&1) ++++sol;
            else ++sol;
        }
    }
    else
    {
        for (long long i=2;i<=r;i<<=1)
            P+=r/i;
        for (long long i=3;i<=r;i*=3)
            Q+=r/i;
        for (i=1;i<(r>>1);++i)
        {
            long long nr=0,num=0;
            for (long long j=2;j<=i;j<<=1)
                nr+=i/j;
            for (long long j=2;j<=r-i;j<<=1)
                nr+=(r-i)/j;
            for (long long j=3;j<=i;j*=3)
                num+=i/j;
            for (long long j=3;j<=r-i;j*=3)
                num+=(r-i)/j;
            if (P>nr && Q>num)
                ++sol;
        }
        sol<<=1;
        long long nr=0,num=0;
        for (long long j=2;j<=r/2;j<<=1)
            nr+=r/2/j;
        for (long long j=2;j<=r-r/2;j<<=1)
            nr+=(r-r/2)/j;
        for (long long j=3;j<=r/2;j*=3)
            num+=r/2/j;
        for (long long j=3;j<=r-r/2;j*=3)
            num+=(r-r/2)/j;
        if (P>nr && Q>num)
        {
            if (r&1) ++++sol;
            else ++sol;
        }
    }
    fout<<sol<<"\n";
    return 0;
}