题目描述

给出三个数a，b，k。

有两种变换方式：

把a变成a−1

把a变成a−a%t，其中2≤t≤k，a%t表示a除以t的余数

求a至少要经过几次变换才能变到b

输入格式

3个正整数a,b,k

输出格式

输出最少变换次数

输入样例 #1

10 1 4

输出样例 #1

6

输入样例 #2

1 1 2

输出样例 #2

0

输入样例 #3

1000000 1 15

输出样例 #3

97798

数据范围与约定

1≤b≤a≤10^6，2≤k≤15。