Roads Around the Farm

Interview

Time limit1sMemory limit128 MB

Summary

Given N cows and a difference K, a group of size s splits into two nonempty groups differing by K when possible; count the final grazing groups.

Level: Medium4 of 10
Topics: Recursion, Math, Divide and conquer, Implementation
Solved: No attempts yet

Problem

Farmer John's cows have taken an interest in exploring the territory around the farm. Initially, all $N$ ( $1 \le N \le 10^9$ ) cows set off down a road together as one big group. When the group reaches a fork in the road, it sometimes breaks into two smaller (nonempty) groups, each continuing down one of the roads. When one of those groups reaches another fork, it may split again, and so on.

The cows split in a peculiar way: if they can divide into two groups whose sizes differ by exactly $K$ ( $1 \le K \le 1000$ ), they split that way; otherwise they stop exploring and begin grazing peacefully.

Assuming the road always provides new forks, compute the final number of groups of peacefully grazing cows.

Input

The first line contains two space-separated integers $N$ and $K$ .

Output

Print a single integer: the number of groups of grazing cows.

Hint

For $N = 6$ and $K = 2$ there are 3 final groups (containing 2, 1, and 3 cows).

Examples1

Example 1
Input
```
6 2
```
Expected output
```
3
```