Интервал

Определите количество чисел, входящих в замкнутый интервал [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}

Входные данные

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

Выходные данные

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

Примеры

Примечание

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.