// how to come up with such solution :(

// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include<bits/stdc++.h>
 
#define int long long
// #define i128 long long
#define double long double
using namespace std;
 
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second

typedef long long ll;
typedef unsigned long long ull;
// typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
int dx[]={1,1,2,2,-1,-1,-2,-2};
int dy[]={2,-2,1,-1,2,-2,1,-1};
// const int mod=1e9+7;
const int INF=LLONG_MAX;
const double EPS=1e-9;
const int N=500007;
const int K=360*10000;
const int mod[2]={998244353,234567899};
const int base[2]={12321,32123};
mt19937 rng(1234);

int b,d;
vi s;

vi mult(vi &s,int t){
    int n=sz(s);
    vi ans(n+18,0);
    int now=0;
    for (int i=0;i<n+18;++i){
        if (i<n) now=now+s[i]*t;
        ans[i]=now%10, now/=10;
    }
    while (!ans.back()) ans.pop_back();
    return ans;
}

bool cmp(vi &l,vi &r){ // l<=r?
    if (sz(l)<sz(r)) return 1;
    if (sz(l)>sz(r)) return 0;
    int n=sz(l);
    for (int i=n-1;i>-1;--i){
        if (l[i]<r[i]) return 1;
        if (l[i]>r[i]) return 0;
    }
    return 1;
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout.precision(15), cerr.precision(15);
    cin>>b>>d;
    string t;
    cin>>t;
    reverse(range(t));
    // rep(i,100000) t.pb('9');
    for (auto c:t) s.pb(c-'0');
    if (d==0){
        vi tt;
        int tmp=b;
        while (tmp) tt.pb(tmp%10), tmp/=10;
        int ans=0;
        while (1){
            int g=__gcd(b,10ll);
            if (g==1) break;
            b/=g;
            tt=mult(tt,10/g);
            if (cmp(tt,s)) {ans++; continue;}
            cout<<ans;
            return 0;
        }
        vi ttmp(sz(tt),0);
        rep(i,sz(tt)) ttmp[i]=s[sz(s)-sz(tt)+i];
        if (cmp(tt,ttmp)) cout<<ans+sz(s)-sz(tt);
        else cout<<ans+sz(s)-sz(tt)-1;
        return 0;
    }
    vi cur,cur9;
    cur.pb(0), cur9.pb(0);
    int ans=0;
    while (1){
        int g=__gcd(b,10ll),idx=-1;
        for (int i=0;i<10/g;++i){
            int fk=(ans?cur9[ans]+1:d);
            if ((9*b*i+fk)%10==0) idx=i;
        }
        if (idx==-1){
            cout<<ans;
            return 0;
        }
        auto add=[&](vi &s,int b,int k){
            int n=sz(s);
            s.resize(max(n,k)+18);
            int now=0;
            for (int i=k;i<max(n,k)+18;++i){
                now=now+b%10+s[i];
                if (now==0&&b==0) break;
                s[i]=now%10, now/=10, b/=10;
            }
            while (!s.back()) s.pop_back();
        };
        add(cur,b*idx,ans), add(cur9,9*b*idx,ans);
        b/=g;
        // cerr<<sz(s)<<endl;
        if (!cmp(cur,s)){
            cout<<ans;
            return 0;
        }
        ans++;
        // for (auto c:cur) cerr<<c<<" ";
        // cerr<<endl;
        // for (auto c:cur9) cerr<<c<<" ";
        // cerr<<endl;
    }
    return 0;
}