PNUPC 1K9

$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을 출력한다.

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