Beaver School in Lviv
The historical center of Lviv is listed in the UNESCO World Heritage Site. The city has the largest number of architectural monuments in Ukraine. In 2009, Lviv was awarded the title of Cultural Capital of Ukraine. The city periodically takes leading places in the ratings of tourist and investment attractiveness.
It is in this beautiful city and right now, from October 27 till November 2, 2013, the first All-Ukrainian school for programming takes place within the framework of the Beaver International Competition in Informatics and Computer Skills.
During the intellectual games of the Beaver school, the participants were given the following task: from the number n get the number m using the minimum number of the following operations:
multiplication by number t;
subtracting a number t, if the current number > t;
division by t, if the current number is divisible by t.
Input
Three positive integers n, m, t (m, n ≤ 100000, 0 < t < 10).
Output
Print the smallest number of operations to get m from n.