#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll inf = 1000000000;
constexpr ll mod = 1000000007;
constexpr long double eps = 1e-9;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << to_string(p.first) << " " << to_string(p.second);
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (ll i = 0; i < (int)v.size(); i++) {
    if (i) os << " ";
    os << to_string(v[i]);
  }
  return os;
}
struct modint {
  ll n;

 public:
  modint(const ll n = 0) : n((n % mod + mod) % mod) {}
  static modint pow(modint a, int m) {
    modint r = 1;
    while (m > 0) {
      if (m & 1) {
        r *= a;
      }
      a = (a * a);
      m /= 2;
    }
    return r;
  }
  modint& operator++() {
    *this += 1;
    return *this;
  }
  modint& operator--() {
    *this -= 1;
    return *this;
  }
  modint operator++(int) {
    modint ret = *this;
    *this += 1;
    return ret;
  }
  modint operator--(int) {
    modint ret = *this;
    *this -= 1;
    return ret;
  }
  modint operator~() const { return (this->pow(n, mod - 2)); }
  friend bool operator==(const modint& lhs, const modint& rhs) {
    return lhs.n == rhs.n;
  }
  friend bool operator<(const modint& lhs, const modint& rhs) {
    return lhs.n < rhs.n;
  }
  friend bool operator>(const modint& lhs, const modint& rhs) {
    return lhs.n > rhs.n;
  }
  friend modint& operator+=(modint& lhs, const modint& rhs) {
    lhs.n += rhs.n;
    if (lhs.n >= mod) lhs.n -= mod;
    return lhs;
  }
  friend modint& operator-=(modint& lhs, const modint& rhs) {
    lhs.n -= rhs.n;
    if (lhs.n < 0) lhs.n += mod;
    return lhs;
  }
  friend modint& operator*=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * rhs.n) % mod;
    return lhs;
  }
  friend modint& operator/=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * (~rhs).n) % mod;
    return lhs;
  }
  friend modint operator+(const modint& lhs, const modint& rhs) {
    return modint(lhs.n + rhs.n);
  }
  friend modint operator-(const modint& lhs, const modint& rhs) {
    return modint(lhs.n - rhs.n);
  }
  friend modint operator*(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * rhs.n);
  }
  friend modint operator/(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * (~rhs).n);
  }
};
istream& operator>>(istream& is, modint m) {
  is >> m.n;
  return is;
}
ostream& operator<<(ostream& os, modint m) {
  os << m.n;
  return os;
}
long long extgcd(long long a, long long b, long long& x, long long& y) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
long long mod_inverse(long long a, long long m) {
  long long x, y;
  if (extgcd(a, m, x, y) == 1)
    return (m + x % m) % m;
  else
    return -1;
}
vector<long long> fact(1010101 + 1, inf);
long long mod_fact(long long n, long long& e) {
  if (fact[0] == inf) {
    fact[0] = 1;
    if (1010101 != 0) fact[1] = 1;
    for (ll i = 2; i <= 1010101; ++i) {
      fact[i] = (fact[i - 1] * i) % mod;
    }
  }
  e = 0;
  if (n == 0) return 1;
  long long res = mod_fact(n / mod, e);
  e += n / mod;
  if ((n / mod) % 2 != 0) return (res * (mod - fact[n % mod])) % mod;
  return (res * fact[n % mod]) % mod;
}
long long mod_comb(long long n, long long k) {
  if (n < 0 || k < 0 || n < k) return 0;
  long long e1, e2, e3;
  long long a1 = mod_fact(n, e1), a2 = mod_fact(k, e2),
            a3 = mod_fact(n - k, e3);
  if (e1 > e2 + e3) return 0;
  return (a1 * mod_inverse((a2 * a3) % mod, mod)) % mod;
}
using mi = modint;
mi mod_pow(mi a, ll n) {
  mi ret = 1;
  mi tmp = a;
  while (n > 0) {
    if (n % 2) ret *= tmp;
    tmp = tmp * tmp;
    n /= 2;
  }
  return ret;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, p;
  cin >> n >> p;
  int ans = inf;
  for (ll i = 0; i < (int)100; i++) {
    n -= p;
    if (n < 0) break;
    bitset<60> bs(n);
    ll mn = bs.count(), mx = n;
    if (mn <= (i + 1) && (i + 1) <= mx) {
      ans = i + 1;
      break;
    }
  }
  if (ans == inf)
    cout << -1 << endl;
  else
    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;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll inf = 1000000000;
constexpr ll mod = 1000000007;
constexpr long double eps = 1e-9;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> p) {
  os << to_string(p.first) << " " << to_string(p.second);
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (ll i = 0; i < (int)v.size(); i++) {
    if (i) os << " ";
    os << to_string(v[i]);
  }
  return os;
}
struct modint {
  ll n;

 public:
  modint(const ll n = 0) : n((n % mod + mod) % mod) {}
  static modint pow(modint a, int m) {
    modint r = 1;
    while (m > 0) {
      if (m & 1) {
        r *= a;
      }
      a = (a * a);
      m /= 2;
    }
    return r;
  }
  modint& operator++() {
    *this += 1;
    return *this;
  }
  modint& operator--() {
    *this -= 1;
    return *this;
  }
  modint operator++(int) {
    modint ret = *this;
    *this += 1;
    return ret;
  }
  modint operator--(int) {
    modint ret = *this;
    *this -= 1;
    return ret;
  }
  modint operator~() const { return (this->pow(n, mod - 2)); }
  friend bool operator==(const modint& lhs, const modint& rhs) {
    return lhs.n == rhs.n;
  }
  friend bool operator<(const modint& lhs, const modint& rhs) {
    return lhs.n < rhs.n;
  }
  friend bool operator>(const modint& lhs, const modint& rhs) {
    return lhs.n > rhs.n;
  }
  friend modint& operator+=(modint& lhs, const modint& rhs) {
    lhs.n += rhs.n;
    if (lhs.n >= mod) lhs.n -= mod;
    return lhs;
  }
  friend modint& operator-=(modint& lhs, const modint& rhs) {
    lhs.n -= rhs.n;
    if (lhs.n < 0) lhs.n += mod;
    return lhs;
  }
  friend modint& operator*=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * rhs.n) % mod;
    return lhs;
  }
  friend modint& operator/=(modint& lhs, const modint& rhs) {
    lhs.n = (lhs.n * (~rhs).n) % mod;
    return lhs;
  }
  friend modint operator+(const modint& lhs, const modint& rhs) {
    return modint(lhs.n + rhs.n);
  }
  friend modint operator-(const modint& lhs, const modint& rhs) {
    return modint(lhs.n - rhs.n);
  }
  friend modint operator*(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * rhs.n);
  }
  friend modint operator/(const modint& lhs, const modint& rhs) {
    return modint(lhs.n * (~rhs).n);
  }
};
istream& operator>>(istream& is, modint m) {
  is >> m.n;
  return is;
}
ostream& operator<<(ostream& os, modint m) {
  os << m.n;
  return os;
}
long long extgcd(long long a, long long b, long long& x, long long& y) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
long long mod_inverse(long long a, long long m) {
  long long x, y;
  if (extgcd(a, m, x, y) == 1)
    return (m + x % m) % m;
  else
    return -1;
}
vector<long long> fact(1010101 + 1, inf);
long long mod_fact(long long n, long long& e) {
  if (fact[0] == inf) {
    fact[0] = 1;
    if (1010101 != 0) fact[1] = 1;
    for (ll i = 2; i <= 1010101; ++i) {
      fact[i] = (fact[i - 1] * i) % mod;
    }
  }
  e = 0;
  if (n == 0) return 1;
  long long res = mod_fact(n / mod, e);
  e += n / mod;
  if ((n / mod) % 2 != 0) return (res * (mod - fact[n % mod])) % mod;
  return (res * fact[n % mod]) % mod;
}
long long mod_comb(long long n, long long k) {
  if (n < 0 || k < 0 || n < k) return 0;
  long long e1, e2, e3;
  long long a1 = mod_fact(n, e1), a2 = mod_fact(k, e2),
            a3 = mod_fact(n - k, e3);
  if (e1 > e2 + e3) return 0;
  return (a1 * mod_inverse((a2 * a3) % mod, mod)) % mod;
}
using mi = modint;
mi mod_pow(mi a, ll n) {
  mi ret = 1;
  mi tmp = a;
  while (n > 0) {
    if (n % 2) ret *= tmp;
    tmp = tmp * tmp;
    n /= 2;
  }
  return ret;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, p;
  cin >> n >> p;
  int ans = inf;
  for (ll i = 0; i < (int)100; i++) {
    n -= p;
    if (n < 0) break;
    bitset<60> bs(n);
    ll mn = bs.count(), mx = n;
    if (mn <= (i + 1) && (i + 1) <= mx) {
      ans = i + 1;
      break;
    }
  }
  if (ans == inf)
    cout << -1 << endl;
  else
    cout << ans << endl;
  return 0;
}

```