1225_C. p-binary_10196
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 ≤ n ≤ 10^9, -1000 ≤ p ≤ 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.
#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int n, p;
  cin >> n >> p;
  long long int f = 0, g = 0;
  for (long long int i = 1; i <= 10000; i++) {
    long long int a = n - (p * i);
    if (a == 1 && i != 1) continue;
    long long int x = 0;
    for (long long int j = 1; j <= i; j++) {
      if (a <= 0) break;
      long long int q = log2(a);
      x = x + pow(2, q);
      a = a - pow(2, q);
      if (a == 0) {
        if (i <= x) f = 1;
        break;
      }
    }
    if (f == 1) {
      cout << i;
      g = 1;
      break;
    }
  }
  if (g == 0) cout << -1;
  return 0;
}

24 0
 1 1
 24 -1
 24 1
 4 -7
 47 23
 17 8
 35 11
 29 9
 5 2
 100500 -179
 13 6
 10 7
 2001 1000
 1 -1000
 1999 999
 536870812 1
 536870911 0
 12345678 -123
 3 -179
 67108838 -1
 101 50
 2 -1000
 3002 1000
 1001 1000
 4 3
 536870812 -1
 678 169
 536870912 0
 3 2
 9 8
 21 10
 16777215 0
 782 156
 9 4
 13 -987
 19 6
 1000000000 1000
 746 248
 1000000000 -1000
 3998 999
 1 -1
 1 1000
 332639425 -399
 11 5
 1 0
 1001 500
 2 1
 47 6
 23 8
 13 11
 938669971 1
 14497105 0
 12345678 -226
 2 -920
 536870812 -2
 9 3
 31 6
 1000000010 -1000
 332639425 -712
 20120098 0
 10103183 -226
 2 -880
 201426349 -2
 536870912 2
 5194733 0
 2666056 -226
 29 11
 2 2
 7 6
 1184 1000
 2162 999
 4 -179
 67108838 -2
 101 75
 3002 1010
 1001 1001
 4 5
 253 169
 536870912 1
 4 2
 4 8
 16777215 -1
 782 160
 13 -205
 240 248
 3295 999
 2 0
 1 1100
 22 5
 1 -2
 1011 500
 2 -1
 6 0
 24 -2
 12 1
 4 0
 93 6
 23 11
 33 11
 2 6
 451 1000
 2162 1332
 3807807 1
 8758503 -2
 101 60
 5424 1010
 1101 1001
 3 3
 253 326
 2 4
 4 6
 29518484 0
 429 160
 9 0
 13 -375
 12 6
 240 202
 1010000000 -1000
 1912 999
 2 -2
 10331180 -712
 34 5
 1111 500
 6 1
 24 -3
 8 1
 93 11
 23 21
 2 11
 1 2
 451 1100
 2162 1908
 3807807 2
 9808602 -2
 001 60
 3 -880
 2190 1010
 1100 1001
 5 3
 201426349 -4
 319 326
 542734098 1
 3 4
 29518484 -1
 429 232
 5 0
 13 -36

2
 -1
 4
 3
 2
 -1
 -1
 -1
 -1
 -1
 8
 -1
 -1
 -1
 8
 -1
 24
 29
 12
 5
 26
 -1
 8
 -1
 1
 1
 26
 -1
 1
 1
 1
 -1
 24
 -1
 -1
 7
 -1
 16
 -1
 14
 -1
 1
 -1
 13
 -1
 1
 -1
 1
 4
 -1
 1
 19
 13
 11
 6
 26
 2
 3
 15
 16
 8
 9
 5
 10
 24
 14
 12
 -1
 -1
 1
 -1
 -1
 4
 13
 -1
 -1
 -1
 -1
 -1
 26
 1
 -1
 1
 4
 4
 -1
 -1
 1
 -1
 2
 2
 -1
 2
 2
 4
 2
 1
 4
 -1
 -1
 -1
 -1
 -1
 11
 13
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 11
 -1
 2
 5
 -1
 -1
 15
 -1
 1
 11
 2
 -1
 2
 3
 2
 4
 1
 -1
 -1
 -1
 -1
 11
 13
 -1
 6
 -1
 -1
 1
 11
 -1
 13
 -1
 12
 -1
 2
 5
