eolymp
bolt
Try our new interface for solving problems
Problems

Интервал

Интервал

Time limit 1 second
Memory limit 64 MiB

Определите количество чисел, входящих в замкнутый интервал [X, Y], представимых в виде суммы различных степеней числа b (для представления любого числа Z[X, Y] каждую степень b можно применить не более одного раза). То есть нужно подсчитать количество Z[X, Y], которые могут быть представлены в виде:

Z = a_nb^n + a_{n-1}b^{n-1} + ... + a_1b^1 + a_0b^0, i, a_i{0, 1}

Input data

В первой строке входного файла содержатся три числа X, Y и b (1XY10^100, 2b10), разделённые пробелами.

Output data

В единственной строке выходного файла выведите количество чисел в интервале [X, Y], представимых в виде суммы различных степеней числа b.

Examples

Input example #1
15 19 4
Output example #1
2

Note

X=4, Y=10, b=3: 4=3^1+3^0; 9=3^2; 10=3^2+3^0

X=1, Y=12, b=2: 1=2^0; 2=2^1; 3=2^1+2^0; 4=2^2; 5=2^2+2^0; 6=2^2+2^1; 7=2^2+2^1+2^0;

8=2^3; 9=2^3+2^0; 10=2^3+2^1; 11=2^3+2^1+2^0; 12=2^3+2^2.

Source SPb ETU Contest, Petrozavodsk, Thursday, August 25, 2005