#include <bits/stdc++.h>
using namespace std;
class bignum {
 private:
  static const int size = 512;
  int ary[size];

 public:
  bignum() {
    for (int i = 0; i < size; i++) {
      ary[i] = 0;
    }
  }
  bignum(int a) {
    for (int i = 0; i < size; i++) {
      ary[i] = 0;
    }
    plus(a);
  }
  int getketa(int a) {
    if (a < size)
      return ary[a];
    else
      return -1;
  }
  void inketa(int a, int k) {
    if (k < size) {
      ary[k] = a;
    }
  }
  void plus(int a) {
    int k = 0;
    while (a != 0) {
      ary[k] += a;
      a = ary[k] / 10;
      if (ary[k] > 9) {
        ary[k] %= 10;
      }
      k++;
    }
  }
  int joyo(int a) {
    int tmp, ttmp;
    int k = size - 4;
    ttmp = 0;
    while (k >= 0) {
      tmp = ttmp * 10000 + ary[k + 3] * 1000 + ary[k + 2] * 100 +
            ary[k + 1] * 10 + ary[k];
      ttmp = tmp % a;
      k -= 4;
    }
    return ttmp;
  }
  bool iszig() {
    int k = size - 1;
    bool z;
    while (ary[k] == 0) {
      k--;
      if (k < 0) return true;
    }
    if (k == 0) return true;
    if (ary[k] < ary[k - 1])
      z = true;
    else if (ary[k] > ary[k - 1])
      z = false;
    else
      return false;
    k--;
    while (k > 0) {
      if (!z && ary[k] < ary[k - 1]) {
        z = true;
      } else if (z && ary[k] > ary[k - 1]) {
        z = false;
      } else {
        return false;
      }
      k--;
    }
    return true;
  }
  int hikaku(bignum &ai) {
    int k = size - 1;
    while (k >= 0) {
      if (ary[k] > ai.ary[k])
        return 1;
      else if (ary[k] < ai.ary[k])
        return -1;
      k--;
    }
    return 0;
  }
};
int main() {
  bignum a, b;
  int cnt, kaz, M;
  stack<int> st;
  char c;
  cnt = 0;
  while (1) {
    cin.get(c);
    if (c == '\n') break;
    st.push(c - '0');
  }
  while (!st.empty()) {
    kaz = st.top();
    a.inketa(kaz, cnt);
    st.pop();
    cnt++;
  }
  cnt = 0;
  while (1) {
    cin.get(c);
    if (c == '\n') break;
    st.push(c - '0');
  }
  while (!st.empty()) {
    kaz = st.top();
    b.inketa(kaz, cnt);
    st.pop();
    cnt++;
  }
  cin >> M;
  cnt = 0;
  int rei;
  rei = a.joyo(M);
  if (rei != 0) {
    a.plus(M - rei);
  }
  while (1) {
    if (a.hikaku(b) == 1) break;
    if (a.iszig()) cnt++;
    if (cnt >= 10000) cnt %= 10000;
    a.plus(M);
  }
  cout << cnt << endl;
  return 0;
}
