Nấm là cô bé đáng yêu và tốt bụng. Cô bé đặc biệt thích truyện cổ tích. Vì thế, đêm qua, Nấm nằm mơ về nàng Lọ Lem. Trong giấc mơ, Lọ Lem không bị mụ dì ghẻ bắt phân loại các loại đậu nữa mà bắt nhặt gạo. Có rất nhiều gạo trong kho, các hạt gạo đã được đánh số thứ tự là số nguyên liên tiếp từ \(a\) tới \(b\). Mụ bắt nàng phải nhặt ra các hạt gạo có số thứ tự là bội của một số \(k\) cho trước. Đồng thời sau khi nhặt xong phải trả lời cho mụ biết số lượng hạt gạo nhặt được. Việc nhặt gạo thì quá đơn giản, chỉ trong tích tắc bầy chim đã giúp nàng nhặt xong. Bây giờ nhiệm vụ của Nấm là đếm số lượng hạt gạo đã nhặt được. Thật không may, chưa đếm xong thì Nấm đã tỉnh dậy. Nấm rất muốn có câu trả lời cho Lọ Lem.

Yêu cầu: Hãy trả lời giúp Nấm, nếu hoàn thành phần việc của mình, Nấm sẽ đếm được bao nhiêu hạt gạo?

Dữ liệu vào:

+ Ba số nguyên dương \(a,\ b\) và \(k\) ghi trên cùng 1 dòng \((1 \leq a \leq b \leq 10^{18};\ 1 \leq k \leq 10^{18})\) .

Kết quả:

+ Ghi một số nguyên duy nhất là kết quả cần tìm.

Ví dụ 1:

Ví dụ 2:

Ràng buộc:

+ 70% số test tương ứng với 70% số điểm có \(1 \leq a \leq b \leq 10^{6}\).

+ 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm.