Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

C. p-binary
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vasya will fancy any number as long as it is an integer power of two. Petya, on the other hand, is very conservative and only likes a single integer $$$p$$$ (which may be positive, negative, or zero). To combine their tastes, they invented $$$p$$$-binary numbers of the form $$$2^x + p$$$, where $$$x$$$ is a non-negative integer.

For example, some $$$-9$$$-binary ("minus nine" binary) numbers are: $$$-8$$$ (minus eight), $$$7$$$ and $$$1015$$$ ($$$-8=2^0-9$$$, $$$7=2^4-9$$$, $$$1015=2^{10}-9$$$).

The boys now use $$$p$$$-binary numbers to represent everything. They now face a problem: given a positive integer $$$n$$$, what's the smallest number of $$$p$$$-binary numbers (not necessarily distinct) they need to represent $$$n$$$ as their sum? It may be possible that representation is impossible altogether. Help them solve this problem.

For example, if $$$p=0$$$ we can represent $$$7$$$ as $$$2^0 + 2^1 + 2^2$$$.

And if $$$p=-9$$$ we can represent $$$7$$$ as one number $$$(2^4-9)$$$.

Note that negative $$$p$$$-binary numbers are allowed to be in the sum (see the Notes section for an example).

Input

The only line contains two integers $$$n$$$ and $$$p$$$ ($$$1 \leq n \leq 10^9$$$, $$$-1000 \leq p \leq 1000$$$).

Output

If it is impossible to represent $$$n$$$ as the sum of any number of $$$p$$$-binary numbers, print a single integer $$$-1$$$. Otherwise, print the smallest possible number of summands.

Examples
Input
24 0
Output
2
Input
24 1
Output
3
Input
24 -1
Output
4
Input
4 -7
Output
2
Input
1 1
Output
-1
Note

$$$0$$$-binary numbers are just regular binary powers, thus in the first sample case we can represent $$$24 = (2^4 + 0) + (2^3 + 0)$$$.

In the second sample case, we can represent $$$24 = (2^4 + 1) + (2^2 + 1) + (2^0 + 1)$$$.

In the third sample case, we can represent $$$24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)$$$. Note that repeated summands are allowed.

In the fourth sample case, we can represent $$$4 = (2^4 - 7) + (2^1 - 7)$$$. Note that the second summand is negative, which is allowed.

In the fifth sample case, no representation is possible.