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)

Input

Several lines, each line contains 2 integers: N and K separated by a single space. (1 < N < 231, 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

Added by:Race with time
Date:2011-02-05
Time limit:0.106s
Source limit:700B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:VOJ

hide comments
2012-07-23 23:54:45 The Vagabond
Input: Several lines??? aWWWWWWWWWWWW.
2011-05-26 10:00:31 cracks
why i am getting time limited exceeded,is there any other algorithm to get binary values of a number in min time,except divisin method,i cant get what part of my solution is taking such a time
2011-02-12 18:27:30 The Bumblebee
What's the criteria for end of input?
2011-02-10 05:35:36 numerix
Is there any good reason for this really strange language restriction? If not, please open it for more/all languages.
Edit: Thanks for opening it for all languages.

Last edit: 2011-02-06 21:08:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.