#include <bits/stdc++.h>
using namespace std;
#define M 10005
void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int Inv(int a,int b){
    int x,y;
    exgcd(a,b,x,y);
    return (x%b+b)%b;
}
char A[M];
int b,d,n;
int Ask(int k,int x){
    // cout<<k<<' '<<x<<endl;
    int g = __gcd(k,b);
    if(x%g!=0)return -1;
    if(1ll*(x/g)*Inv(k/g,b/g)%(b/g) == 0 && d == 0) return b/g;
    return 1ll*(x/g)*Inv(k/g,b/g)%(b/g);
}
int pre[M];
bool check(int x,int p){//x,d...d
    static int P[M];
    int len=0;
    for(;x;x/=10)P[++len]=x%10;
    reverse(P+1,P+1+len);
    for(int i=1;i<=len;i++)
        if(P[i]+'0'!=A[i])
            return P[i]+'0'<A[i];
    if(pre[len+1] == n+1)return 1;
    return d+'0' < A[pre[len+1]];
}
int main(){
    cin>>b>>d;
    scanf("%s",A+1);
    n=strlen(A+1);
    pre[n+1]=n+1;
    for(int i=n;i>=1;i--)
        if(A[i]!='0'+d)pre[i]=i;
        else pre[i] = pre[i+1];
    
    int tt=1, md=0;
    //x * tt + md %b == 0
    int ans = -1;
    for(int p=0;p<=n;p++){
        int x = Ask(tt,(b-md)%b);
        if(x!=-1){
            assert((1ll*x*tt+md)%b==0);
            int leng = 0,last=x;
            while(x)leng++,x/=10;
            if(leng + p > n);
            else if(leng + p < n)ans = p;
            else if(check(last,p))ans = p;
        }
        
        tt=10ll*tt%b;
        md = (10ll*md+d)%b;
    }
    cout<<ans<<endl;
    return 0;
}