题目描述

给定$x,y,k$三个正整数，每次可以选择以下操作之一

操作1：$x=x-1$

操作2：$x=\frac{x}{k}$，当且仅当$x$是$k$的倍数。

薯条哥想要将$x$变为$y$，并希望操作次数最少，请你帮帮他。

输入描述

一行输入三个整数$x,y,k(1\le y\le x\le 10^9,1\le k\le 10^9)$

输出描述

一个正整数，表示最小操作次数

样例

输入

10 4 2

输出

2