SP8265 ZEROCNT - Zero Count

Write down N integers 1, 2, ..., N in binary system on a paper, one per line, ignore all leading 0s: 1 10 11 100 101 110 111 ... Now on each line, consider all groups of consecutive 0s, index these group from 1. We will color all zeros in the 1st, (K+1)th, (2K+1)th, ... group, for K is a given integer. For example: if a number in binary is: 10100011100110000, and K = 2. We have 4 groups of consecutive 0s, and we will color all zeros in the 1st and the 3rd group. So we will color 1 + 2 = 3 zeros in this line. Given N and K. Compute total number of 0s we will color in the paper. (The paper is big enough to contain all numbers :D)

Several lines, each line contains 2 integers: N and K separated by a single space. (1 < N < 2 $ ^{31} $ , K > 0)

For each line in the input, print exactly 1 number on a single line which is the result of the corresponding test case.