#include<bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
ll n, x, nr, k;
ll desc(ll a)
{
    ll maxim=-1;
    if(!(a & 1))
    {
        while(!(a & 1))
            a=a>>1;
        maxim=2;
    }
    ll d=3;
    while(d*d<=a)
    {
        if(a%d==0)
        {
            while(a%d==0)
                a/=d;
            if(maxim<d) maxim=d;
        }
        d+=2;
    }
    if(a>1 && maxim<a) maxim=a;
    return maxim;
}
int main()
{
    for(int i=1; i<=10; i++)
    {
        nr=0;
        f>>x>>k;
        ll r=desc(k);
        for(int j=r; j<=x; j+=r)
        {
            int q=j;
            while(q%r==0)
            {
                q/=r;
                nr++;
            }
        }
        g<<nr<<'\n';
    }
    return 0;
}