Кошмар

면접 대비

시간 제한2초메모리 제한1024 MB

요약

a에서 시작해 d 이하의 정수 k로 곱하거나 나누되 나눗셈은 나누어떨어질 때만 가능할 때, b에 도달하는 최소 연산 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 정수론, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

Вчера ночью Мамаю приснился кошмар. Во сне его капитал сначала уменьшался в несколько раз, потом увеличивался, потом снова уменьшался, в общем, кошмар.

К сожалению, Мамай не запомнил сон полностью. Все, что он помнит --- то, что с его капиталом происходили только два действия:

Капитал увеличивался ровно в $k$ раз, где $k$ --- натуральное число, причем $k \le d$
Капитал уменьшался ровно в $k$ раз, где $k$ --- натуральное число, причем $k \le d$ (размер капитала должен делиться нацело на число $k$ )

Также Мамай помнит три числа $a, b, d$ --- размер капитала в начале сна, в конце сна и число $d$ , которое ограничивает коэффициент изменения капитала.

Он уже не сможет вспомнить весь сон полностью, поэтому все, что он просит --- найти минимальное количество действий, которое могло произойти с его начальным капиталом --- числом $a$ , чтобы после них получился конечный капитал --- число $b$ .

Помогите Мамаю --- у него слишком много дел, а этот сон не дает ему покоя.

입력

В первой и единственной строке входного файла дано три числа $a, b, d$ ( $1 \le a, b, d \le 10^9$ ) --- числа, которые запомнил Мамай.

출력

В единственной строке выходного файла выведите минимальное количество действий, за которое можно получить число $b$ из числа $a$ с помощью описанных операций.

Если такой последовательности действий не существует, выведите -1.

예제4

예제 1
입력
```
3 5 5
```
예상 출력
```
2
```
예제 2
입력
```
2 4 2
```
예상 출력
```
1
```
예제 3
입력
```
1 8 3
```
예상 출력
```
3
```
예제 4
입력
```
1 3 2
```
예상 출력
```
-1
```