#include <stdio.h>
#define INF 2000000000

inline long long sum(int n, int p){
  int k = n / p;
  return 1LL * k * (k - 1) * p / 2 + 1LL * (n - k * p + 1) * k;
}

inline long long calc(int b, int j, int n){
  int q, cj;
  long long p;
  q = 0;
  while(b % j == 0){
    b /= j;
    q++;
  }
  p = 0;
  cj = j;
  while(n / j >= cj){
    p += sum(n, cj);
    cj *= j;
  }
  p += sum(n, cj);
  return p / q;
}

int main(){
  FILE *in = fopen("zero2.in", "r");
  FILE *out = fopen("zero2.out", "w");
  int i, j, n, b;
  long long x, min;
  for(i = 0; i < 10; i++){
    fscanf(in, "%d%d", &n, &b);
    min = INF;
    for(j = 2; j * j <= b; j++){
      if(b % j == 0){
        x = calc(b, j, n);
        if(min > x)
          min = x;
        while(b % j == 0)
          b /= j;
      }
    }
    if(b > 1){
      x = calc(b, b, n);
      if(min > x)
        min = x;
    }
    fprintf(out, "%lld\n", min);
  }
  fclose(in);
  fclose(out);
  return 0;
}