시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB228644325.444%

문제

$10$진수는 $0$에서 $9$까지 숫자를 사용해 수를 나타내지만 진법에 따라서 알파벳을 사용하기도 한다. 예를 들어 $16$진수는 A부터 F까지 6개의 알파벳을 $10$부터 $15$까지 나타내는 데 사용해 수를 표기할 수 있다. $10$진수 95는 $16$진수로 5F와 같이 표기할 수 있다. $36$진수는 A부터 Z까지 26개의 알파벳을 $10$부터 $35$까지 나타내는 데 사용해 수를 표기할 수 있다. $10$진수 71은 $36$진수 1Z와 같이 표기할 수 있다.

$36$진수로 표기된 양의 정수 $s$와 $10$진수로 표기된 양의 정수 $k$, $p$가 주어질 때 $s$의 자릿값을 수정해 $s \equiv k \pmod {p}$가 성립하도록 해 보자. 자릿값을 수정할 때 길이를 늘이거나 줄일 수 없으나 가장 큰자리 숫자를 $0$으로 수정할 수도 있다.

입력

첫 번째 줄에 36진수로 표기된 양의 정수 $s$가 주어진다. ($1 \leq s < 36^{100 \, 000}$)

두 번째 줄에 10진수로 표기된 양의 정수 $k$, $p$가 공백으로 구분되어 주어진다. ($0 \leq k < p \leq 1\, 000$)

출력

$s \equiv k \pmod {p}$를 만족하게 하는 최소 수정 횟수를 출력한다. 만약 어떤 방법으로도 만족하게 할 수 없다면 대신 -1을 출력한다.

예제 입력 1

8W
1 5

예제 출력 1

1

예제 입력 2

85
5 16

예제 출력 2

0

예제 입력 3

1
36 37

예제 출력 3

-1

노트

36진수 1K9는 10진수로 2025$(1 \times 36^2 + K \times 36 + 9)$이다.