You are given three positive integers p, q, and r. In one operation you may pick either p or q and do one of the following to it:

• increment it by 1, or
• divide it by r, rounding down (x becomes floor(x / r)).

Operations may be applied to either value, in any order, any number of times. Return the minimum number of operations needed to make p and q equal.

Examples

Example 1

Input: p = 5, q = 1, r = 2
Output: 2
Explanation: Divide p twice: 5 -> 2 -> 1.

Example 2

Input: p = 2, q = 10, r = 3
Output: 2
Explanation: Divide q once (10 -> 3), then increment p once (2 -> 3).

Example 3

Input: p = 4, q = 4, r = 10
Output: 0
Explanation: The values are already equal.