Giải bài trực tuyến

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/degree

Một số nguyên dương A gọi là có bậc K đối với cơ số B nếu như :
• A = B^x1 + B^x2 + … + B^xk
( trong đó x1 , x2 , … , xk là các số nguyên không âm thoả mãn x1 <> x2 <> x3 … <> xk )
Ví dụ :
• 17 có bậc 2 đối với cơ số 2 vì 17 = 2^4 + 2^0 .
• 151 có bậc 3 đối với cơ số 5 vì 151 = 5^3 + 5^2 + 5^0.
Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.
Giới hạn :
• 1 <= X <= Y <= 10^9
• 1 <= K <= 25, 2 <= B <= 9
• Chạy được với bộ nhớ thông báo < 800 K bạn mới thực sự là thành công

Input

1 dòng gồm 4 số nguyên dương X , Y , K , B

Output

Gồm 1 dòng duy nhất ghi ra số lượng số tìm được .

Example

Input:
15 20 2 2

Output:
3 

( Giải thích : Đó là các số 17 = 2^4 + 2^0 , 18 = 2^4 + 2^1 , 20 = 2^4 + 2^2 )