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^{x_1} + B^{x_2} + \ldots + B^{x_k}$$

Trong đó ~x_1,x_2, \ldots, x_k~ là các số nguyên không âm thoả mãn ~x_1 \ne x_2 \ne x_3 \ne \ldots \ne x_k~

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~.

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 .

Giới hạn

• ~1 \le X \le Y \le 10^9~.
• ~1 \le K \le 25;\text{ } 2 \le B \le 9~
• Chạy được với bộ nhớ thông báo bé hơn ~800~ ~KB~ bạn mới thực sự là thành công

Sample Input

15 20 2 2

Sample Output

3