#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <array>
#include <queue>
#include <cmath>
#include <iomanip>
#include <iterator>
#include <bitset>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <chrono>
#include <random>
#include <functional>
#include <random>
#include <complex>

using namespace std;
using namespace std::chrono;

class InputReader {
public:
    InputReader() {
        input_file = stdin;
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }

    InputReader(const char *file_name) {
        input_file = fopen(file_name, "r");
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }

    template<typename T>
    inline InputReader &operator>>(T &n) {
        while ((buffer[cursor] < '0' || buffer[cursor] > '9') && buffer[cursor] != '-') {
            advance();
        }
        int sign = 1;
        if (buffer[cursor] == '-') {
            sign = -1;
            advance();
        }
        n = 0;
        while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
            n = n * 10 + buffer[cursor] - '0';
            advance();
        }
        n *= sign;
        return *this;
    }

    inline InputReader &operator>>(char *s) {
        while (!isalpha(buffer[cursor])) {
            advance();
        }
        int len = 0;
        while (isalpha(buffer[cursor])) {
            s[len] = buffer[cursor];
            len++;
            advance();
        }
        s[len] = 0;
        return *this;
    }

private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    int cursor;
    char buffer[SIZE];

    inline void advance() {
        ++cursor;
        if (cursor == SIZE) {
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
    }
};

string toString(int x) {
    string ans = "";
    while (x > 0) {
        ans.push_back('0' + x % 10);
        x /= 10;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

bool ok(int l, int b, int d, const string &a) {
    int p10 = 1, suf = 0;
    for (int i = 1; i <= l; i++) {
        p10 = (p10 * 10) % b;
        suf = (suf * 10 + d) % b;
    }
    // need X * p10 + suf = 0 (mod b)
    for (int x = (d == 0 ? 1 : 0); x <= b; x++) {
        if ((1LL * x * p10 + suf) % b == 0) {
            string xs = toString(x);
            if (xs.size() + l < a.size()) {
                return true;
            } else if (xs.size() + l > a.size()) {
                return false;
            } else {
                string n = xs + string(l, '0' + d);
                assert(n.size() == a.size());
                return n <= a;
            }
        }
    }
    return false;
}

int main() {
    //ifstream cin("input.txt");
//    ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    srand(time(0));

    int b, d;
    string a;
    cin >> b >> d >> a;
    int left = 1, right = a.size(), ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (ok(mid, b, d, a)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << ans << "\n";

//    auto stopTime = high_resolution_clock::now();
//    auto duration = duration_cast<milliseconds>(stopTime - startTime);
//    cout << "Ellapsed time: " << duration.count() << "\n";
    return 0;
}