Задача E. Цветные нули

Автор:XII Командный чемпионат школьников Санкт-Петербурга по программированию   Ограничение времени:2 сек
Входной файл:zeroes.in   Ограничение памяти:8 Мб
Выходной файл:zeroes.out  

Условие

Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2,…, n. Получились числа 1, 10, 11, 100, 101, 110, 111, …

После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число k и в каждой строке, идя слева направо, выделил красным цветом каждый k-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, k + 1, 2 k + 1, … Например если k = 2, n = 56, то получились бы такие строки:

1 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0
1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1
1 1 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0
1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1
1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 1 1
1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0
(красные нули выделены жирным шрифтом и подчеркнуты)

Теперь Толику интересно, сколько же ноликов он выделил. Помогите ему их посчитать.

Формат входного файла

Во входном файле содержатся числа n и k .

Формат выходного файла

Выходной файл должен содержать одно число — количество красных нулей.

Ограничения

1 ≤ n < 231, 1 ≤ k ≤ 30

Примеры тестов

Входной файл (zeroes.in) Выходной файл (zeroes.out)
1
4 1
3
2
56 2
74

0.040s 0.007s 15