#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

int dis[1000005];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    auto cmp = [](string a, string b) {
        if (SZ(a) != SZ(b)) return SZ(a) < SZ(b);  
        return a < b;
    };

    int b, d;
    string a;
    cin >> b >> d >> a;

    auto check = [&](int mid) {
        string s = string(mid, d + '0');
        if (cmp(a, s)) return 0;
        fill(dis, dis + b, -1);
        int x = 0, tn = 1;
        for (int i = 0; i < mid; ++i)
            x = (x * 10 + d) % b, tn = tn * 10 % b;
        int cur = 0, cnt = 0;
        if (d == 0) cur = tn, ++cnt;
        while (dis[cur] == -1)
            dis[cur] = cnt, cur = (cur + tn) % b, ++cnt;
        if (dis[(b - x) % b] == -1) return 0;
        if (dis[(b - x) % b] > 0)
            s = to_string(dis[(b - x) % b]) + s;
        if (cmp(a, s)) return 0;
        return 1;
    };

    int l = 0, r = SZ(a) + 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << l << "\n";
}