Trailing Digits

많은 양의 장신구가 방금 도착했고, 각 장신구의 권장 소비자 가격은 b센트다. 소비자들은 끝자리가 대부분 같은 가격일 때 물건을 훨씬 더 자주 구매한다는 사실을 알아냈다. 예를 들어, 물건은 57센트보다 99센트로 가격이 매겨질 때 더 잘 팔린다. 따라서 상품을 더 매력적으로 만들기 위해 상품을 묶음으로 판매하기로 했다. 묶음을 만들려면 양의 정수 k를 선택하고, k개의 장신구를 k × b센트에 판다. 적절한 k를 선택하면 더 보기 좋은 가격을 만들 수 있다. 예를 들어, 57센트짜리 장신구를 크기 7의 묶음으로 팔면 각 묶음은 399센트에 팔리며, 이는 57의 끝자리 9가 없는 것보다 두 개의 끝자리 9를 가진다. 이 끝자리 9에 대한 아이디어는 다른 끝자리 숫자로도 일반화할 수 있다: 57센트짜리 장신구 692개 묶음은 39,444센트(끝자리 4가 세 개)에 팔리고, 백만 개 묶음은 57,000,000센트(끝자리 0이 여섯 개)에 팔린다.

잠시 생각해보면, 묶음을 너무 크게 만들고 싶지 않다는 것을 알게 된다. 가격이 지나치게 높아질 뿐만 아니라, 누가 정말로 수백만 개의 장신구를 필요로 하겠는가? 모든 유형의 장신구에 대해, 마케팅 부서는 최대 묶음 가격 a를 정했다.

장신구의 가격, 원하는 끝자리 숫자, 묶음의 최대 가격이 주어졌을 때, 끝자리 숫자를 최적화하는 프로그램을 작성하시오.

입력은 세 개의 정수 b, d, a를 포함하는 단일 줄로 구성된다. 여기서 b (1 ≤ b < 10^6)는 장신구의 가격(센트), d (0 ≤ d ≤ 9)는 원하는 끝자리 숫자, a (b ≤ a < 10^10,000)는 묶음의 최대 가격이다.

묶음 가격이 a를 초과할 수 없다는 조건 하에, 묶음 가격의 끝에 나타날 수 있는 d의 최대 연속 발생 횟수를 출력하시오.