题目描述

小猴想通过以下两种变换，把 $1$ 变成 $b$。

1.把现有的数 $x$ 变为 $x+d$。

2.把现有的数 $x$ 变为 $px+1$。

例如 $b=43,d=10,p=3$，你可以以如下的方式把 $1$ 变成 $b$。

$1×3+1=4$

$4+10=14$

$14×3+1=43$

你需要帮小猴判断一下，把 $1$ 变成 $b$ 最少需要多少次变换。

输入格式

$3$ 个正整数 $b,d,p$。

输出格式

输出最小操作次数，如果无法变换成 $b$ 输出 -1。

样例输入输出

43 10 3

3

说明/提示

$1 \leq b \leq 10^6$

$1 \leq d,p \leq 100$