Mã hóa - ENCRYPTION

Khi nghiên cứu xây dựng thuật toán mã hóa, Nam cần giải quyết bài toán sau: Với bốn số nguyên dương ~L, R, A, K,~ cần đếm số lượng số nguyên dương ~S~ mà ~L ≤ S ≤ R~ và ~(A * S)~ ~mod~ ~K~ ~= 0~, trong đó ~mod~ là phép toán chia lấy dư.

Hãy giúp Nam giải bài toán trên.

Yêu cầu:

Đếm số lượng số nguyên dương ~S~ thỏa yêu cầu bài toán

Dữ liệu (Vào từ tệp ENCRYPTION.INP):

• Dòng duy nhất chứa ~4~ số nguyên dương ~L, R, A, K~ ~(1 ≤ L, R, A, K ≤ 10^{18}; L ≤ R)~.

Kết quả (Xuất ra tệp ENCRYPTION.OUT):

• Gồm một số nguyên dương duy nhất là kết quả bài toán

Ví dụ:

1 10 2 10

2

Subtask:

• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~1~ ~≤ L, R, K ≤~ ~10^6~ và ~A = 1~.
• ~40\%~ số test tương ứng với ~40\%~ số điểm có ~1~ ~≤ L, R, A, K ≤~ ~10^6~.
• ~30\%~ số test còn lại tương ứng với ~30\%~ số điểm không có ràng buộc gì thêm.