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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define int long long int
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define ln '\n'

const int MOD = 1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int fastpow(ll a, ll p, ll mod){
	if(p==0) return 1;
	ll z = fastpow(a, p/2, mod);
	z = (z * z) % MOD;
	if(p%2) z = (a * z) % MOD;
	return z;
}

int b, d;
string a;

bool str_smaller(string a, string b){
	int ptr1 = 0;
	int ptr2 = 0;

	while((ptr1 < a.size()) && (a[ptr1]=='0')){
		ptr1 ++;
	}
	while((ptr2 < b.size()) && (b[ptr2]=='0')){
		ptr2 ++;
	}

	int l1 = (int)a.size() - ptr1, l2 = (int)b.size() - ptr2;
	if(l1>l2) return 0;
	if(l1<l2) return 1;

	string s1 = a.substr(ptr1, l1), s2 = b.substr(ptr2, l2);
	return (s1 <= s2);
}

bool check(int last_rep){

	int f1 = 1;
	int f2 = 0;
	rep(i, 0, last_rep){
		f2 += f1;
		f1 = (f1 * 10) % b;
	}
	f2 = (f2 * d) % b;
	bool pos = 0;
	rep(i, 0, b){
		if((i==0)&&(d==0)) continue;
		if((f1 * i + f2) % b == 0){
			string s = to_string(i);
			rep(j, 0, last_rep) s += ('0'+d);
			if(str_smaller(s, a)) pos = 1;
			break;	
		}
	}
	return pos;
}


signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	cin >> b >> d >> a;
	
	int l = 0, r = 1000000;

	while(l < r){
		int mid = (l+r+1)/2;
		if(check(mid)){
			l = mid;
		}
		else{
			r = mid - 1;
		}
	}	

	cout << l << endl;


	return 0;
}