Trong đợt hội trại 26/3 vừa qua, Đoàn thanh niên trường THPT chuyên ABC đã tổ chức rất nhiều trò chơi thú vị. Trong đó, có trò chơi chỉnh lí như sau:

Cho mỗi người chơi 1 số \(A\) là trạng thái nguy hiểm. Yêu cầu người chơi phải tìm cách thoát khỏi trạng thái nguy hiểm này bằng cách chuyển giá trị số ban đầu thành \(B\) là trạng thái an toàn. Có 2 phương án chuyển: nâng \(A\) lên \(1\) giá trị hoặc nâng \(A\) lên \(2\) giá trị. Trong quá trình nâng, phải tránh việc giá trị sau khi nâng là bội số của \(C\) là trạng thái có khả năng cao rơi vào nguy hiểm.

Người chơi thắng cuộc là người chơi có số lần nâng tối thiểu để từ giá trị \(A\) có được giá trị \(B\) trong thời gian quy định. Người chơi cảm thấy khó khăn khi gặp các giá trị \(A, B\) quá lớn, họ không thể thử tất cả các trường hợp.

Yêu cầu: Các bạn học sinh giỏi tin hãy tìm cách tính số lần nâng ít nhất.

Input

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

Output

• Ghi một số nguyên là số lần nâng ít nhất.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(A, B, C \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(A, B, C \leq 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): \(A, B, C \leq 10^9\).

Example

4 10 3 

4