Một con robot thám hiểm sao hỏa tên là \(Mars Rover\) của cơ quan vũ trụ Nga đã không hoạt động. Để khôi phục nó, cần phải tăng thêm công suất cho pin. Pin của Rover là một số nguyên dương. Công suất hiện tại của pin là \(a\), để khôi phục hoạt động của nó, cần phải tăng công suất của nó lên giá trị \(b\).

Từ trái đất, có hai loại tín hiệu đặc biệt có thể gửi đến con Rover để thay đổi công suất pin: Tín hiệu \(X\) và Tín hiệu \(Y\). Tín hiệu \(X\) làm tăng công suất của pin lên \(1\), tín hiệu \(Y\) làm tăng công suất của pin lên \(2\). Các chuyên gia hàng không vũ trụ Liên Bang muốn thay đổi công suất pin theo yêu cầu, nhưng phải gửi đi số lượng ít nhất tín hiệu. Thật không may, do đặc thù thiết kế của con Rover, nếu công suất của pin là bội số của một số nguyên \(c\), thì nó sẽ bị lỗi và ngừng hoạt động.

Yêu cầu: Cho công suất pin ban đầu là \(a\), công suất pin yêu cầu là \(b\) và một số nguyên \(c\), hãy xác định số lượng tín hiệu ít nhất phải được truyền tới rover để cho nó hoạt động mà không bị gặp lỗi.

Dữ liệu:

• Gồm một dòng chứa 3 số nguyên \(a,b,c\) trên một dòng \((1≤a<b≤10^9,2 ≤c≤10^9), a,b\) không phải là bội của \(c\).

Kết quả:

• Ghi ra một số nguyên duy nhất là số tín hiệu ít nhất cần truyền tới Rover.

Ràng buộc:

• Có 25% số điểm có \(1≤a<b≤15,2≤c≤15;\)

• Có 25% số điểm có \(1≤a<b≤10^5,2≤c≤10^5;\)

• Có 25% số điểm có \(1≤a<b≤10^9,c=2;\)

• Có 25% số điểm có \(1≤a<b≤10^9,2≤c≤10^9.\)

Sample Input

2 7 3

Sample Output

3

Sample Input

4 10 3

Sample Output

4

Giải thích:

• Ở ví dụ thứ nhất các bước truyền tín hiệu sẽ như sau: 2 -> 4 -> 5 -> 7

• Ở ví dụ thứ hai các bước truyền tín hiệu sẽ như sau: 4 -> 5 -> 7 -> 8 -> 10