#include <stdio.h>
int r,d,rez;
int e[5000005];
void calcul (int x)
{
    int y=x,nr=0;
    while (x)
    {
        nr+=x/d;
		x/=d;
    }
    e[y]=nr;
}
int calcul6 (int x)
{
    int y=x,nr=0;
    while (x)
    {
        nr+=x/d;
		x/=d;
    }
    return nr;
}
void check_prim (int n)
{
	int i;
    for (i=0; i<=n; ++i)
    {
        if (!e[r-i])
            calcul (r-i);
        if (!e[i])
            calcul (i);
        if (e[r]-e[r-i]-e[i]>0)
            rez+=2;
    }
}

void check_prim4 (int n)
{
	int i;
    for (i=0; i<=n; ++i)
    {
        if (!e[r-i])
            calcul (r-i);
        if (!e[i])
            calcul (i);
        if ((e[r]-e[r-i]-e[i])/2>0)
            rez+=2;
    }
}
int min (int a,int b)
{
    if (a<b)
        return a;
    else 
        return b;
}
void check_prim6 (int n)
{
	int i,m2,m3;
    for (i=0; i<=n; ++i)
    {
        if (!e[r-i])
        {
            d=2;
            m2=calcul6 (r-i);
            d=3;
            m3=calcul6 (r-i);
            e[r-i]=min (m2,m3);
        }
        if (!e[i])
        {
            d=2;
            m2=calcul6 (i);
            d=3;
            m3=calcul6 (i);
            e[i]=min (m2,m3);
        }
        if (e[r]-e[r-i]-e[i]>0)
            rez+=2;
    }
}
int main ()
{
    freopen ("pascal.in","r",stdin);
    freopen ("pascal.out","w",stdout);
    int m2,m3;
    scanf ("%d%d",&r,&d);
    if (r%2==1 && (d==2 || d==3 ||d==5))
    {
        calcul (r);
        check_prim (r/2);
    }
    else if (r%2==0 && (d==2 || d==3 ||d==5))
    {
        calcul (r);
        check_prim (r/2-1);
        if (!e[r/2])
            calcul (r/2);
        if (e[r]-2*e[r/2]>0)
            ++rez;
	}
	else if (r%2==1 && d==4)
	{
        d=2;
        calcul (r);
        check_prim4 (r/2);
    }
    else if (r%2==0 && d==4)
    {
        d=2;
        calcul (r);
        check_prim4 (r/2-1);
        if (!e[r/2])
            calcul (r/2);
        if ((e[r]-e[r/2]-e[r/2])/2>0)
            ++rez;
	}
	else if (r%2==1 && d==6)
	{
        d=2;
        m2=calcul6 (r);
        d=3;
        m3=calcul6 (r);
        e[r]=min (m2,m3);
        check_prim6 (r/2);
    }
    else if (r%2==0 && d==6)
    {
        d=2;
        m2=calcul6 (r);
        d=3;
        m3=calcul6 (r);
        e[r]=min (m2,m3);
        check_prim6 (r/2-1);
        if (!e[r/2])
        {
            d=2;
            m2=calcul6 (r/2);
            d=3;
            m3=calcul6 (r/2);
            e[r/2]=min (m2,m3);
        }
        if (e[r]-e[r/2]-e[r/2]>0)
            ++rez;
	}
	printf ("%d",rez);
	return 0;
}