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)

Input

Several lines, each line contains 2 integers: N and K separated by a single space. (1 < N < 2³¹, K > 0)

Output

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

Example

Input:
4 1
56 2
Output:
3
92