提示: 欢迎访问OurACM平台。
Problem 1624 Revival's split

Accept: 102    Submit: 155
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Farmer John's cows have taken an interest in exploring the territory around the farm. Initially, all N (1 <= N <= 1,000,000,000) cows commence traveling down a road in one big group. Upon encountering a fork in the road, the group sometimes chooses to break into two smaller (nonempty) groups with each group continuing down one of the roads. When one of those groups arrives at another fork, it might split again, and so on.

The cows have crafted a peculiar way of splitting: if they can split into two groups such that the sizes of the groups differ by exactly K (1 <= K <= 1000), then they will split in that way; otherwise, they stop exploring and just start grazing peacefully.

Assuming that there will always be new forks in the road, compute the final number of groups of peacefully grazing cows.

Input

There are multiple tests.

For each test, there are two space-separated integers: N and K.

Output

For each test, output a single integer representing the number of groups of grazing cows.

Sample Input

6 2

Sample Output

3

Hint

INPUT DETAILS:

There are 6 cows and the difference in group sizes is 2.

OUTPUT DETAILS:

There are 3 final groups (with 2, 1, and 3 cows in them).


   6
  / \
 2   4
    / \
   1   3

Source

Summer Training Qualification I

Submit  Back  Status  Discuss