시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

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

После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число $k$ и в каждой строке, идя слева направо, выделил красным цветом каждый $k$-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами $1, k + 1, 2k + 1, \ldots$ Например если $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 \le n < 2^{31}$, $1 \le k \le 30$).

출력

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

예제 입력 1

4 1

예제 출력 1

3

예제 입력 2

56 2

예제 출력 2

74