// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops", "omit-frame-pointer", "inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
// #pragma GCC option("arch=native", "no-zero-upper") // Enable AVX

/// UH Top
#include <bits/stdc++.h>
#define db(x) cerr << #x << ':' << (x) << '\n';
#define all(v) (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
#define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t int128;
typedef pair<ll, ll> pii;
typedef pair<ld, ll> pdi;
typedef pair<ld, ld> pdd;
typedef pair<ld, pdd> pdp;
typedef pair<string, ll> psi;
typedef pair<ll, string> pls;
typedef pair<string, string> pss;
typedef pair<ll, pii> pip;
typedef pair<pii, pii> ppp;
typedef complex<ld> point;
typedef vector<point> polygon;
typedef vector<ll> vi;
typedef pair<point, int> ppi;
#define prec(n)        \
    cout.precision(n); \
    cout << fixed
const ll mod = (1e9 + 7);
const ld eps = (1e-9);
const ll oo = (ll)(1e18 + 5);
#define pi acos(-1)
#define MAXN (ll)(1e6 + 5)

ll gcd(ll a, ll b, ll &x, ll &y)
{
	if(b == 0)
		return x = 1, y = 0, a;
	ll r = gcd(b, a % b, y, x);
	y -= a / b * x;
	return r;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll b,d;
    string a;
    cin >> b >> d >> a;
    vector<int> cmp(a.size()+1);
    reverse(all(a));
    cmp[0]=1;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]>'0'+d)
            cmp[i+1]=1;
        else if(a[i]<'0'+d)
            cmp[i+1]=-1;
        else
            cmp[i+1]=cmp[i];
    }

    ll mul=1;
    ll res=0;
    for(int i=1;i<=a.size();i++)
    {
        mul=(mul*10)%b;
        res=(res*10+d)%b;

        ll fal=(b-res)%b;
        ll x,y;
        ll g=gcd(mul,b,x,y);
        // cout << '\n';
        // cout << mul << ' ' << fal << ' ' << g << '\n';
        if(fal%g)
        {
            cout << i-1 << '\n';
            return 0;
        }
        if(i+10<a.size())
            continue;
        ll v1=b/g;
        ll m1=mul/g;
        fal/=g;
        if(x>=0)
            x%=v1;
        else
            x=(v1-((-x)%v1))%v1;
        x=(x*fal)%v1;
        if(!d && !x)
        {
            x=v1;
        }
        ll max=0;
        for(int j=a.size()-1;j>=i;j--)
            max=(max*10+a[j]-'0');
        if(cmp[i]==-1)
            max--;
        // cout << max << ' ' << x << '\n';
        if(max<x)
        {
            cout << i-1 << '\n';
            return 0;
        }
    }
    cout << a.size() << '\n';

    return 0;
}