Ground Is Lava

Windra has just won gold in the Olympic pole vault, and in the rush of excitement they leave the stadium still carrying their pole. Then they hear that their long-lost brother Bindra is waiting somewhere in the Olympic village. Windra starts at point $a$, Bindra is at point $b$, and every point in the village is represented by an integer on a number line.

Windra can move in two ways:

• For every integer $x$, they may walk between points $x$ and $x+1$.
• For every integer $x$, there are vault pads at points $kx$ and $k(x+1)$, and Windra may use the pole to launch between these two points.

Each walk or vault takes exactly one minute.

Given $k$, $a$, and $b$, find the minimum number of minutes Windra needs to reach Bindra.

Input

The only line contains three integers $k$, $a$, and $b$ ($1 \leq k \leq 10^9$, $-10^9 \leq a, b \leq 10^9$), in this order.

Output

Print one integer: the minimum number of minutes needed to get from point $a$ to point $b$.

Example 1

4 1 10

5

Explanation

In the sample, one optimal route is: