#include <bits/stdc++.h>
using namespace std;
long long mod = (long long)1 << 50;
long long QPow(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) ans = ans % mod * a % mod;
    a = a % mod * a % mod;
    b >>= 1;
  }
  return ans;
}
long long gcd(long long x, long long y) {
  if (x == 1 || y == 1)
    return 1;
  else {
    if (x == 0) return y;
    if (y == 0) return x;
    if (x % y == 0) return y;
    if (y % x == 0) return x;
    if (x > y)
      return gcd(x % y, y);
    else
      return gcd(x, y % x);
  }
}
string toString(long long a) {
  if (a == 0) return "0";
  string temp = "";
  if (a < 0) temp.push_back('-');
  long long tp = a;
  while (tp) {
    temp.push_back('0' + tp % 10);
    tp /= 10;
  }
  string temp2 = temp;
  for (int ii = 0; ii < temp.size(); ii++) {
    temp[ii] = temp2[temp.size() - 1 - ii];
  }
  return temp;
}
long long inf = INT_MAX;
const int maxn = 1e2 + 5;
int cnt = 0;
int head[maxn], dep[maxn], fa[maxn][22];
long long dis[maxn];
struct edge {
  int v, nx;
  long long val;
} es[maxn << 1];
void add(int u, int v, int w) {
  es[cnt].v = v;
  es[cnt].nx = head[u];
  es[cnt].val = w;
  head[u] = cnt++;
}
void dfs0(int u, int f, long long ds) {
  dis[u] = ds;
  for (int i = head[u]; i != -1; i = es[i].nx) {
    int v = es[i].v;
    if (v == f) continue;
    dfs0(v, u, ds + es[i].val);
  }
}
void dfs(int u, int f) {
  dep[u] = dep[f] + 1;
  fa[u][0] = f;
  for (int i = 1; (1 << i) <= dep[u]; i++) {
    fa[u][i] = fa[fa[u][i - 1]][i - 1];
  }
  for (int i = head[u]; i != -1; i = es[i].nx) {
    int v = es[i].v;
    if (v != f) dfs(v, u);
  }
}
int lca(int a, int b) {
  if (dep[a] > dep[b]) swap(a, b);
  for (int i = 20; i >= 0; i--)
    if (dep[a] <= dep[b] - (1 << i)) b = fa[b][i];
  if (a == b) return a;
  for (int i = 20; i >= 0; i--) {
    if (fa[a][i] == fa[b][i])
      continue;
    else
      a = fa[a][i], b = fa[b][i];
  }
  return fa[a][0];
}
int last1[200005];
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ifstream in("Text.txt");
  long long p, n, m;
  int t;
  cin >> n >> p;
  long long ans = 0;
  for (long long i = 0;; i++) {
    int ct = 0;
    long long temp = n - i * p;
    if (temp < 0) {
      cout << -1 << endl;
      return 0;
    }
    while (temp) {
      ct += temp % 2;
      temp >>= 1;
    }
    if (i >= ct && n - i * p >= i && n != i * p) {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long mod = (long long)1 << 50;
long long QPow(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) ans = ans % mod * a % mod;
    a = a % mod * a % mod;
    b >>= 1;
  }
  return ans;
}
long long gcd(long long x, long long y) {
  if (x == 1 || y == 1)
    return 1;
  else {
    if (x == 0) return y;
    if (y == 0) return x;
    if (x % y == 0) return y;
    if (y % x == 0) return x;
    if (x > y)
      return gcd(x % y, y);
    else
      return gcd(x, y % x);
  }
}
string toString(long long a) {
  if (a == 0) return "0";
  string temp = "";
  if (a < 0) temp.push_back('-');
  long long tp = a;
  while (tp) {
    temp.push_back('0' + tp % 10);
    tp /= 10;
  }
  string temp2 = temp;
  for (int ii = 0; ii < temp.size(); ii++) {
    temp[ii] = temp2[temp.size() - 1 - ii];
  }
  return temp;
}
long long inf = INT_MAX;
const int maxn = 1e2 + 5;
int cnt = 0;
int head[maxn], dep[maxn], fa[maxn][22];
long long dis[maxn];
struct edge {
  int v, nx;
  long long val;
} es[maxn << 1];
void add(int u, int v, int w) {
  es[cnt].v = v;
  es[cnt].nx = head[u];
  es[cnt].val = w;
  head[u] = cnt++;
}
void dfs0(int u, int f, long long ds) {
  dis[u] = ds;
  for (int i = head[u]; i != -1; i = es[i].nx) {
    int v = es[i].v;
    if (v == f) continue;
    dfs0(v, u, ds + es[i].val);
  }
}
void dfs(int u, int f) {
  dep[u] = dep[f] + 1;
  fa[u][0] = f;
  for (int i = 1; (1 << i) <= dep[u]; i++) {
    fa[u][i] = fa[fa[u][i - 1]][i - 1];
  }
  for (int i = head[u]; i != -1; i = es[i].nx) {
    int v = es[i].v;
    if (v != f) dfs(v, u);
  }
}
int lca(int a, int b) {
  if (dep[a] > dep[b]) swap(a, b);
  for (int i = 20; i >= 0; i--)
    if (dep[a] <= dep[b] - (1 << i)) b = fa[b][i];
  if (a == b) return a;
  for (int i = 20; i >= 0; i--) {
    if (fa[a][i] == fa[b][i])
      continue;
    else
      a = fa[a][i], b = fa[b][i];
  }
  return fa[a][0];
}
int last1[200005];
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ifstream in("Text.txt");
  long long p, n, m;
  int t;
  cin >> n >> p;
  long long ans = 0;
  for (long long i = 0;; i++) {
    int ct = 0;
    long long temp = n - i * p;
    if (temp < 0) {
      cout << -1 << endl;
      return 0;
    }
    while (temp) {
      ct += temp % 2;
      temp >>= 1;
    }
    if (i >= ct && n - i * p >= i && n != i * p) {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

```