#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int b,d;
string a;
const int maxn=1e6+10;
int ddd[maxn];
int Iooo[maxn];
void solve() {
    cin>>b>>d>>a;
    
    int ans;
    int l=0;
    int r=a.size();
    Iooo[0]=1;
    for(int i=1;i<maxn;i++){
        ddd[i]=(ddd[i-1]*10+d)%b;
        Iooo[i]=Iooo[i-1]*10%b;
    }
    while(l<=r){
        int mid=l+r>>1;
        string tmp(mid,d+'0');
        int x=Iooo[mid];
        int y=ddd[mid];
        int t=y;
        int best=-1;
        int ibegin;
        if(d==0){
            ibegin=1;
            t+=x;
            if(t>=b)t-=b;
        }
        else{
            ibegin=0;
        }
        for(int i=ibegin;i<b+ibegin;i++){
            if(t==0){
                best=i;
                break;
            }
            t+=x;
            if(t>=b)t-=b;
        }
        int ok;
        if(best==-1)ok=0;
        else{
            string k;
            if(best==0){
                k=tmp;
            }
            else{
                k=to_string(best);
                k+=tmp;
            }
            if(k.size()!=a.size()){
                if(k.size()<a.size())ok=1;
                else ok=0;
            }
            else{
                if(k<=a)ok=1;
                else ok=0;
            }
        }
        if(ok){
            ans=mid,l=mid+1;
        }
        else r=mid-1;
    }    
    cout<<ans<<"\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}