#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 5;
int b, n, d, dig[maxn], pw[maxn];
char s[maxn];
int main() {
    scanf("%d%d%s", &b, &d, s + 1);
    n = 2e4;
    pw[0] = 1;
    for(int i = 1; i <= n; ++ i) {
        pw[i] = (pw[i - 1] * 10) % b;
    }
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++ i) {
        dig[i] = s[i] - '0';
    }
    if(d != 0) {
        if(b % 10 == 0) {
            puts("0");
            return 0;
        }
        if(b % 5 == 0 && d != 5) {
            puts("0");
            return 0;
        }
        if(b % 25 == 0) {
            puts(d == 5 ? "1" : "0");
            return 0;
        }
        if(b % 2 == 0 && d % 2 != 0) {
            puts("0");
            return 0;
        }
        int th = 0;
        if(b % 4 == 0 && (d == 2 || d == 6)) {
            th = 1;
        }
        if(b % 8 == 0 && d == 4) {
            th = 2;
        }
        if(b % 16 == 0 && d == 8) {
            th = 3;
        }
        if(th) {
            int ans = 0;
            for(int i = th; i >= 1; -- i) {
                if(n - i >= 7) {
                    ans = i;
                    break;
                }
                else {
                    int rem = 0;
                    for(int j = 0; j < i; ++ j) {
                        rem = (rem + pw[j] * d) % b;
                    }
                    int lim = 0;
                    for(int j = n - i + 1; j <= n; ++ j) {
                        if(dig[j] > d) {
                            break;
                        }
                        else if(dig[j] < d) {
                            lim = 1;
                            break;
                        }
                    }
                    int x = 0;
                    for(int j = 1; j <= n - i; ++ j) {
                        x = x * 10 + dig[j];
                    }
                    int flg = 0;
                    for(int j = 0; j <= x - lim; ++ j) {
                        if((rem + 1ll * pw[i] * j) % b == 0) {
                            flg = 1;
                            break;
                        }
                    }
                    if(flg) {
                        ans = i;
                        break;
                    }
                }
            }
            printf("%d\n", ans);
            return 0;
        }
    }
    int lim = 0;
    if(n > 7) {
        for(int i = 8; i <= n; ++ i) {
            if(dig[i] > d) {
                break;
            }
            else if(dig[i] < d) {
                lim = 1;
                break;
            }
        }
    }
    int x = 0;
    for(int i = 1; i <= min(n, 7); ++ i) {
        x = x * 10 + dig[i];
    }
    int rem = 0, ans = d == 0 ? 0 : 0;
    for(int i = n; i > 7; -- i) {
        rem = (rem + pw[n - i] * d) % b;
    }
    for(int i = 0; i <= x - lim; ++ i) {
        if(!d && !i)
            continue;
        if((rem + 1ll * pw[max(0, n - 7)] * i) % b == 0) {
            int c = 0, tmp = i;
            while(tmp && tmp % 10 == d) {
                ++ c;
                tmp /= 10;
            }
            ans = max(ans, max(0, n - 7) + c);
        }
    }
    printf("%d\n", ans);
}