화성에서 국제 임무를 수행하는 탐사차가 고장 났습니다. 작동을 복구하려면 배터리 출력을 높여야 합니다.

탐사차의 배터리 출력은 양의 정수로 주어집니다. 현재 출력은 $a$이며, 탐사차의 작동을 복구하려면 이를 $b$까지 높여야 합니다. 배터리 출력을 바꾸기 위해 지구에서 탐사차로 X와 Y 두 종류의 특수 신호를 보낼 수 있습니다. X 신호는 현재 배터리 출력을 $1$만큼 높이고, Y 신호는 현재 배터리 출력을 $2$만큼 높입니다.

임무 주최 측은 가능한 한 적은 신호를 보내 필요한 배터리 출력에 도달하고자 합니다. 하지만 탐사차의 구조 때문에 배터리 출력이 정수 $c$의 배수가 되면 탐사차는 완전히 고장 나서 더 이상 신호에 응답하지 않습니다.

초기 배터리 출력 $a$, 필요한 배터리 출력 $b$, 정수 $c$가 주어졌을 때 탐사차의 작동을 복구하기 위해 보내야 하는 신호의 최소 개수를 구하는 프로그램을 작성하세요.

입력

입력에는 세 정수 $a$, $b$, $c$가 한 줄에 하나씩 주어집니다 ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; $a$와 $b$는 모두 $c$의 배수가 아닙니다).

출력

탐사차로 보내야 하는 신호의 최소 개수를 정수 하나로 출력하세요.

예제

입력 1

2
7
3

출력 1

3

입력 2

4
10
3

출력 2

4

참고

첫 번째 예제에서는 Y, X, Y 신호를 보낼 수 있습니다. 배터리 출력은 $2 \to 4 \to 5 \to 7$로 변합니다.

두 번째 예제에서는 X, Y, X, Y 신호를 보낼 수 있습니다. 배터리 출력은 $4 \to 5 \to 7 \to 8 \to 10$으로 변합니다.

서브태스크

각 서브태스크와 그에 필요한 서브태스크의 모든 테스트를 통과한 경우에만 해당 서브태스크의 점수를 받습니다.