III Open Distance Programming Olympiad name V.L.Didkovsky 2013-2014

Beaver School in Lviv

Time limit 1 second
Memory limit 128 MiB

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 data

Three positive integers n, m, t (m, n100000, 0 < t < 10).

Output data

Print the smallest number of operations to get m from n.


Input example #1
2 3 3
Output example #1
Author Sergiy Zhukovskiy
Source 2013 - 2014 III Open Distant Olympiad named by V.L.Didkovsky