#include <bits/stdc++.h>
const double PI = acos(-0);
const int mod = 1000007;
const int maxn = 1e6 + 10;
const int inf = 0x3f;
const int NEXT[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
using namespace std;
long long a[maxn];
const int temp = 360360;
int main() {
  long long aa, bb, k;
  while (scanf("%lld%lld%lld", &aa, &bb, &k) != EOF) {
    scanf("%lld%lld%lld", &aa, &bb, &k);
    memset((a), (inf), (sizeof(a)));
    a[360360 + aa % 360360] = 0;
    for (long long i = 360360 + aa % 360360; i; i--) {
      a[i - 1] = min(a[i - 1], a[i] + 1);
      for (long long j = 2; j <= k; j++)
        if (i % j) a[i - i % j] = min(a[i] + 1, a[i - i % j]);
    }
    long long ans;
    if ((aa / 360360 == bb / 360360))
      ans = a[bb % 360360 + 360360] - a[aa % 360360 + 360360];
    else
      ans = ((aa / 360360 - bb / 360360 - 1) * (a[1] - a[360361])) +
            a[(bb % 360360)] - a[aa % 360360 + 360360];
    printf("%I64d", ans);
  }
}
