Spirit là robot tự hành do NASA phóng lên để thám hiểm bề mặt sao hỏa. Do hoạt động lâu nên robot bị hỏng nguồn. Để khôi phục khả năng hoạt động của robot cần nâng công suất pin của nó lên. Công suất pin của robot được cho bởi một số nguyên dương. Công suất hiện tại là ~a~, để khôi phục khả năng hoạt động của robot cần tăng công suất lên thành ~b~. Để thay đổi công suất pin của robot, từ Trái đất có thể truyền hai loại tín hiệu: ~X~ và ~Y~ . Tín hiệu loại ~X~ cho phép tăng công suất hiện tại lên ~1~, tín hiệu loại ~Y~ cho phép tăng công suất hiện tại lên ~2~.

Các kỹ sư NASA mong muốn sử dụng ít số lần truyền tin nhất để sửa được lỗi cho robot. Tuy nhiên, do đặc thù cấu tạo của robot, nếu công suất pin tại một thời điểm nào đó là bội của số nguyên ~c~ thì robot sẽ hỏng hoàn toàn và không tương tác với tín hiệu điều khiển nữa.

Yêu cầu: Cho trước các số nguyên ~a, b, c~, hãy xác định số lần gửi tín hiệu tối thiểu để khôi phục được khả năng hoạt động của robot.

Dữ liệu vào

Một dòng duy nhất chứa ~3~ số nguyên ~a, b, c~ ~(1 ≤ a < b ≤ 10^9, 2 ≤ c ≤ 10^9, a~ không chia hết cho ~c~, và ~b~ không chia hết cho ~c)~.

Dữ liệu ra

Xác định số lần gửi tín hiệu tối thiểu để có thể khôi phục được khả năng hoạt động của robot.

Giới hạn

• Có 25% số lượng test tương ứng 25% số điểm thỏa mãn ~1 ≤ a < b ≤ 15, 2 ≤ c ≤ 15~;
• Có 25% số lượng test tương ứng 25% số điểm thỏa mãn ~1 ≤ a < b ≤ 10^5, 2 ≤ c ≤ 10^5~;
• Có 25% số lượng test tương ứng 25% số điểm thỏa mãn ~1 ≤ a < b ≤ 10^9, c = 2~;
• 25% số lượng test còn lại tương ứng 25% số điểm thỏa mãn ~1 ≤ a < b ≤ 10^9, 2 ≤ c ≤ 10^9~.

Sample Input 1

2
7
3

Sample Output 1

3

Sample Input 2

4
10
3

Sample Output 2

4

Giải thích

• Trong ví dụ thứ nhất, cần truyền 3 tín hiệu loại lần lượt là ~Y, X, Y~ . Công suất robot lần lượt tăng như sau: ~2 → 4 → 5 → 7~.
• Trong ví dụ thứ hai, cần truyền 4 tín hiệu loại lần lượt là ~X, Y, X, Y~ . Công suất robot lần lượt tăng như sau: ~4 → 5 → 7 → 8 → 10~.

Nguồn: Trại đông Bảo Lộc 2021 - thầy Đỗ Phan Thuận