29134번 - Кошмар 다국어

문제

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

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

• Капитал увеличивался ровно в $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.

제한

힌트