火星で国際ミッションを遂行している探査車が故障しました。動作を回復させるには、バッテリーの出力を増やす必要があります。

探査車のバッテリー出力は正の整数で表されます。現在の出力は $a$ であり、探査車の動作を回復させるには $b$ まで増やす必要があります。バッテリー出力を変えるため、地球から探査車へ X と Y の 2 種類の特別な信号を送れます。X 型の信号は現在のバッテリー出力を $1$ 増やし、Y 型の信号は $2$ 増やします。

ミッションの主催者は、できるだけ少ない信号でバッテリー出力を必要な値にしたいと考えています。しかし、探査車の構造上、バッテリー出力が整数 $c$ の倍数になると、探査車は完全に故障し、信号に反応しなくなります。

初期バッテリー出力 $a$、必要なバッテリー出力 $b$、整数 $c$ が与えられたとき、探査車の動作を回復させるために送る必要がある信号の最小数を求めるプログラムを作成してください。

入力

入力には整数 $a$、$b$、$c$ が 1 行に 1 個ずつ含まれます（$1 \le a < b \le 10^9$、$2 \le c \le 10^9$、$a$ と $b$ はどちらも $c$ の倍数ではありません）。

出力

探査車に送る必要がある信号の最小数を 1 個の整数として出力してください。

入出力例

入力 1

2
7
3

出力 1

3

入力 2

4
10
3

出力 2

4

注記

最初の例では、探査車に Y、X、Y の順に信号を送れます。バッテリー出力は $2 \to 4 \to 5 \to 7$ と変わります。

2 番目の例では、探査車に X、Y、X、Y の順に信号を送れます。バッテリー出力は $4 \to 5 \to 7 \to 8 \to 10$ と変わります。

小課題

各小課題の得点は、その小課題と必要な小課題のすべてのテストに合格した場合にのみ与えられます。