Một xe tự hành đang thực hiện nhiệm vụ quốc tế trên Sao Hỏa bị hỏng. Để khôi phục hoạt động của xe, cần tăng công suất pin của nó.

Công suất pin của xe được biểu diễn bằng một số nguyên dương. Công suất hiện tại là $a$, và để khôi phục hoạt động của xe, cần tăng công suất lên $b$. Có thể gửi từ Trái Đất tới xe các tín hiệu đặc biệt thuộc hai loại X và Y để thay đổi công suất pin. Tín hiệu loại X tăng công suất hiện tại thêm $1$, còn tín hiệu loại Y tăng công suất hiện tại thêm $2$.

Ban tổ chức nhiệm vụ muốn đạt công suất pin cần thiết bằng cách gửi ít tín hiệu nhất có thể. Đáng tiếc, do đặc điểm thiết kế của xe, nếu công suất pin trở thành bội của số nguyên $c$, xe sẽ hỏng hoàn toàn và ngừng phản hồi các tín hiệu.

Hãy viết chương trình, với công suất pin ban đầu $a$, công suất cần thiết $b$ và số nguyên $c$ cho trước, xác định số tín hiệu ít nhất cần gửi tới xe để khôi phục hoạt động của nó.

Dữ liệu vào

Dữ liệu vào gồm ba số nguyên $a$, $b$ và $c$, mỗi số trên một dòng ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; cả $a$ và $b$ đều không là bội của $c$).

Dữ liệu ra

In ra một số nguyên: số tín hiệu ít nhất cần gửi tới xe.

Ví dụ

Dữ liệu vào 1

2
7
3

Dữ liệu ra 1

3

Dữ liệu vào 2

4
10
3

Dữ liệu ra 2

4

Ghi chú

Trong ví dụ thứ nhất, có thể gửi tới xe các tín hiệu Y, X, Y. Công suất pin thay đổi như sau: $2 \to 4 \to 5 \to 7$.

Trong ví dụ thứ hai, có thể gửi tới xe các tín hiệu X, Y, X, Y. Công suất pin thay đổi như sau: $4 \to 5 \to 7 \to 8 \to 10$.

Nhiệm vụ con

Chỉ nhận được điểm của một nhiệm vụ con khi vượt qua mọi kiểm thử của nhiệm vụ đó và các nhiệm vụ con bắt buộc.