题目描述

小珅想通过以下两种变换，把 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。

输入样例 #1

5571 10 10

输出样例 #1

17

输入样例 #2

1 1 1

输出样例 #2

0

输入样例 #3

1000000 100 100

输出样例 #3

-1

数据范围与约定

1≤b≤$10^{6}$，1≤d,p≤100。