#include <cstdio>
#include <fstream>
#include <math.h>

using namespace std;

#define FIN "zero2.in"
#define FOUT "zero2.out"
#define ll long long

typedef struct 
 {
    ll n;
    int p;
 } structure;

ll B,N;
ll Rez;
int pra[800000];
int pr[100000];
structure d[1<<10];
ll M[1<<10];

  void preprocesare()
  {
     int i,k;
     int lim=800000;
     memset(pra,0,sizeof(pra));
     memset(pr,0,sizeof(pr));
     for (i=2; i<=int(sqrt(lim)); i++)
      {
        k=i*i;
        while (k<=lim) { pra[k]=1; k+=i; }
      }  
     k=0;
     for (i=2; i<=lim; i++)
      if (!pra[i]) pr[++k]=i;
     return ; 
  }    
     
  ll NR (ll n, ll p)
  {
     ll k;
     ll ret=0,P=p;
     while (P<=n)
      {
        k=n/P-1;
        ret+=(long long)(k*(k+1)/2*P);
        ret+=(long long)((k+1)*(n-(k+1)*P+1));   
        P*=p;
      }
     return ret;
  }      
          
      
  void solve (void)
  {
     int i=1;
     ll p=0;
     ll c;
     memset(d,0,sizeof(d));
     ll m=B;
     while (i<=1<<19 && m!=1)
      {
       if (pr[i]!=0)   
        if (m%pr[i]==0)
         {         
           d[++p].n=pr[i]; c=0;
           while (m%pr[i]==0) { m/=pr[i]; c++; }
           d[p].p = c;
         }
        i++;
      }
     if (m>1) { d[++p].n=m;  d[p].p=1; }      
     for (i=1; i<=p; i++)
      {
        c=NR(N,d[i].n);
        if (d[i].p!=0) M[i]=(long long)(c/d[i].p);
         else M[i]=1000000000;
      }
     Rez = 1000000000;
     for (i=1; i<=p; i++)
      if (M[i]<Rez) Rez=(long long)M[i];          
  }    
  

  int main()
  { 
       freopen(FIN,"r",stdin);
       freopen(FOUT,"w",stdout);
       
       int x;
       preprocesare();
       
       for (x=1; x<=10; x++)
        {
          scanf("%lld %lld",&N,&B);
          
          solve ();
          
          printf("%lld\n",Rez);
        }
        
       fclose(stdin); fclose(stdout);
       return 0;
  }