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.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, gcd, log
import bisect
import sys
import copy

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def find_ones(n):
	cnt = 0
	while n:
		if n & 1:
			cnt += 1
		n //= 2
	return cnt
(n, p) = get_ints()
ok = False
for i in range(1, 35):
	num = n - p * i
	if num < 0:
		break
	ans = find_ones(num)
	if ans <= i and num >= i:
		print(i)
		ok = True
		break
if not ok:
	print(-1)


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, p) = map(int, input().split())
(ans, i) = (-1, 1)
while True:
	n -= p
	if n <= 0:
		break
	if bin(n).count('1') <= i and i <= n:
		ans = i
		break
	i += 1
print(ans)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
from math import gcd

def dtb(n):
	return bin(n).replace('0b', '')
(n, p) = map(int, input().split())
ans = 0
while ans < 50:
	ck = n - p * ans
	if ck >= 1:
		tot1 = 0
		tot2 = 0
		t = dtb(ck)
		for (i, v) in enumerate(reversed(t)):
			if v == '1':
				tot1 += 1
				tot2 += 2 ** i
		if tot1 <= ans <= tot2:
			break
	ans += 1
if ans < 50:
	print(ans)
else:
	print(-1)


(n, p) = [int(x) for x in input().split()]
l = 1
for mid in range(1, 32):
	k = n - mid * p
	u = 0
	if k < mid:
		continue
	for i in range(50, -1, -1):
		if k >= 2 ** i:
			k -= 2 ** i
			u += 1
		if k == 0:
			break
	if u <= mid and u != 0:
		print(mid)
		break
else:
	print(-1)


def set_bits(n):
	cout = 0
	while n > 0:
		if n & 1 == 1:
			cout += 1
		n >>= 1
	return cout
flag = 0
(n, p) = map(int, input().split())
for i in range(65):
	num = n - i * p
	ans = set_bits(num)
	if i >= ans and i <= num:
		flag = 1
		break
if flag == 0:
	print(-1)
else:
	print(i)


(n, p) = map(int, input().split())
ans = -1
m = 1
if p == 0:
	s = bin(n)[2:]
	for i in range(len(s)):
		if s[i] == '1':
			ans += 1
	ans += 1
while n - m * p > 0 and p != 0:
	k = n - m * p
	(left, right) = (0, 0)
	s = bin(k)[2:]
	for i in range(len(s)):
		if s[i] == '1':
			left += 1
			right += 1
		if i > 0 and s[i - 1] == '1' and (s[i] == '0'):
			s = s[:i] + '1' + s[i + 1:]
			right += 1
	if left <= m <= right:
		ans = m
		break
	m += 1
print(ans)


(n, m) = map(int, input().split())
i = 1
count = 0
flag = 0
while True:
	count = 0
	if n - m * i <= 0:
		flag = 1
		break
	str = bin(n - m * i).replace('0b', '')
	for j in str:
		if j == '1':
			count += 1
	if i >= count and i <= n - m * i:
		break
	i += 1
if flag == 1:
	print(-1)
else:
	print(i)


def bn(x):
	b = []
	i = 1
	j = 0
	while j < 32:
		b.append(int(x & i != 0))
		i = i << 1
		j += 1
	b.reverse()
	return sum(b)
(n, p) = map(int, input().split())
for i in range(1, 32):
	bi = bn(n - i * p)
	if bi <= i <= n - i * p:
		print(i)
		exit()
print(-1)


def Find(n, k):
	sum = k
	A = [1 for i in range(k)]
	i = k - 1
	while i >= 0:
		while sum + A[i] <= n:
			sum += A[i]
			A[i] *= 2
		i -= 1
	if sum != n:
		return -1
	else:
		return 0
(n, p) = map(int, input().split())
k = 1
f = 0
while k <= 40:
	if Find(n - p * k, k) == 0:
		f = 1
		break
	k += 1
if f == 1:
	print(k)
else:
	print(-1)


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi
from collections import deque, defaultdict
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7

def get_val(n):
	i = 0
	while n:
		i += n & 1
		n >>= 1
	return i
(n, k) = R()
k *= -1
p = 0
if k == 0:
	exit(print(get_val(n)))
while n:
	p += 1
	n += k
	if n <= 0:
		exit(print(-1))
	if get_val(n) <= p <= n:
		exit(print(p))


def f(x):
	return range(sum([int(e) for e in bin(x)[2:]]), x + 1)

def main():
	(n, p) = [int(e) for e in input().split()]
	b = 1
	while n - b * p >= 0:
		d = f(n - b * p)
		if b in d:
			print(b)
			return
		if b > d[-1]:
			break
		b += 1
	print(-1)
main()


(n, p) = [int(i) for i in input().split()]
i = 1
f = True
while n - i * p >= 1:
	if bin(n - i * p)[2:].count('1') <= i and i <= n - i * p:
		print(i)
		f = False
		break
	i += 1
if f:
	print('-1')


(n, p) = map(int, input().split())
i = 1
while 1:
	m = n - p * i
	if m <= 0:
		break
	if i > m:
		i += 1
		continue
	pc = bin(m).count('1')
	if pc <= i:
		print(i)
		exit()
	i += 1
print(-1)


(n, p) = list(map(int, input().split()))
ans = -1
l = 1
while n - l * p > 0:
	if p == 0:
		s = bin(n)[2:]
		for i in range(len(s)):
			if s[i] == '1':
				ans += 1
		ans += 1
		break
	k = n - l * p
	(v1, v2) = (0, 0)
	s = bin(k)[2:]
	for i in range(len(s)):
		if s[i] == '1':
			v1 += 1
			v2 += 1
		if i > 0 and s[i - 1] == '1' and (s[i] == '0'):
			v2 += 1
			s = s[:i] + '1' + s[i + 1:]
	if v1 <= l <= v2:
		ans = l
		break
	l += 1
print(ans)


import math
(x, y) = map(int, input().split())
i = 1
n = x - i * y
while n >= 1:
	a = 0
	for j in str(bin(n))[2:]:
		a += int(j)
		a *= 2
	a //= 2
	if str(bin(n))[2:].count('1') <= i and i <= a:
		print(i)
		break
	i += 1
	n = x - i * y
else:
	print(-1)


(n, p) = map(int, input().split())
ans = -1
i = 1
while True:
	n -= p
	if n < i:
		print(ans)
		break
	k = str(bin(n)[2:]).count('1')
	if i >= k:
		print(i)
		break
	i += 1


(n, p) = map(int, input().split())
for i in range(1, 100):
	x = n - i * p
	if x <= 0:
		print(-1)
		exit()
	if bin(x).count('1') <= i <= x:
		print(i)
		exit()
print(-1)
exit()


(n, p) = map(int, input().split())
for i in range(1, 33):
	k = n - i * p
	if k >= i and bin(abs(k)).count('1') <= i:
		print(i)
		exit(0)
print(-1)


(n, p) = map(int, input().split())
ans = 1
while n:
	n -= p
	if n < ans:
		print(-1)
		break
	if bin(n).count('1') <= ans:
		print(ans)
		break
	ans += 1
else:
	print(-1)


(n, p) = list(map(int, input().split()))
for q in range(5757):
	s = bin(n)
	if n >= q >= s.count('1'):
		print(q)
		break
	n -= p
else:
	print(-1)


from math import log

def col(n):
	rez = 0
	while n > 0:
		rez += n % 2
		n //= 2
	return rez

def f(n, p):
	for i in range(1, int(log(n, 2) + 20)):
		if col(n - p * i) == i:
			return i
		if col(n - p * i) < i and n - p * i >= i:
			return i
	return -1
(n, p) = list(map(int, input().split()))
print(f(n, p))


(n, p) = [int(x) for x in input().split()]
from math import log
f = 0

def check(x, i):
	t = list(bin(x))[2:]
	if t.count('1') <= i:
		return True
	return False
i = 0
for i in range(0, 100):
	if check(n - i * p, i) and n - i * p >= i:
		print(i)
		f = 1
		break
if f == 0:
	print(-1)


out = -1
(n, p) = [int(i) for i in input().split()]
for i in range(1, 10000, 1):
	if n - p * i < i:
		break
	answer = str(bin(n - p * i)[2:]).count('1')
	if answer <= i and answer != 0:
		out = i
		break
print(out)


(n, p) = map(int, input().split())
l = 1
k = 1
while n - l * p > 0:
	s = bin(n - l * p)[2:]
	l1 = 0
	l2 = 0
	last = 0
	for i in s:
		if i == '1':
			l1 += 1
			l2 += 1
			last = 1
		elif last > 0:
			l2 += 2 ** (last - 1)
			last += 1
	if l >= l1 and l2 >= l:
		print(l)
		k = 0
		break
	l += 1
if k:
	print(-1)


(n, p) = map(int, input().split())
for m in range(1, 10000):
	x = n - m * p
	b = bin(x)
	if b.count('1') <= m <= x:
		print(m)
		exit()
print(-1)


import sys
import bisect
import heapq
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def numofBits(n):
	ans = 0
	while n > 0:
		rem = n % 2
		n = n // 2
		if rem == 1:
			ans += 1
	return ans
(n, p) = Ri()
flag = False
minn = INF
for i in range(32):
	n += -p
	if n <= 0:
		break
	temp = numofBits(n)
	if temp <= i + 1 and n >= i + 1:
		minn = min(minn, i + 1)
		flag = True
if flag:
	print(minn)
else:
	print(-1)


(n, p) = map(int, input().split())
c = 1
while n:
	n -= p
	if n < c:
		print(-1)
		break
	if bin(n).count('1') <= c:
		print(c)
		break
	c += 1


import sys

def count_1(n):
	ans = 0
	while n > 0:
		if n % 2 == 1:
			ans += 1
		n //= 2
	return ans
(n, p) = list(map(int, input().split()))
for i in range(1, 40):
	n -= p
	if n <= 0:
		break
	if count_1(n) <= i and n >= i:
		print(i)
		return
print(-1)


from math import log2
(n, p) = input().split()
n = int(n)
p = int(p)
k = 1
u = 1
while n - p * k >= 1:
	if log2(n - p * k) + 1 >= k >= bin(n - p * k).count('1'):
		print(k)
		u = 0
		break
	else:
		k += 1
if u:
	print(-1)


ls = list(map(int, input().split()))
n = ls[0]
p = ls[1]
k = 1
success = False
if p > 0:
	while n - k * p > 0:
		x = str(bin(n - k * p))[2:]
		count1 = 0
		for j in x:
			if j == '1':
				count1 += 1
		if count1 <= k and k <= n - k * p:
			print(k)
			success = True
			break
		k += 1
	if success == False:
		print(-1)
elif p == 0:
	x = str(bin(n))[2:]
	count1 = 0
	for j in x:
		if j == '1':
			count1 += 1
	if count1 > 0:
		print(count1)
	else:
		print(-1)
elif p < 0:
	while success == False:
		while n - k * p < 0:
			k += 1
		x = str(bin(n - k * p))[2:]
		count1 = 0
		for j in x:
			if j == '1':
				count1 += 1
		if count1 <= k and k <= n - k * p:
			print(k)
			success = True
			break
		k += 1


def Dec_to_Bin(N):
	b = ''
	while N > 0:
		b = str(N % 2) + b
		N = N // 2
	if b == '':
		return '0'
	return b
if True:
	(n, p) = list(map(int, input().split()))
	j = 1
	while True:
		if n - p * j <= 0:
			print(-1)
			break
		S = Dec_to_Bin(n - p * j)
		if S.count('1') <= j:
			ans = 0
			k = 0
			while k < len(S):
				ans += int(S[k]) * 2 ** (len(S) - k - 1)
				k += 1
			if ans >= j:
				print(j)
			else:
				print(-1)
			break
		j += 1


(n, p) = [int(j) for j in input().split()]
for i in range(1, 32):
	if n - i * p >= i:
		ct = bin(n - i * p)[2:].count('1')
		if ct <= i:
			print(i)
			break
else:
	print(-1)


def get_n(bin_n):
	ans = 0
	while bin_n > 0:
		ans += bin_n & 1
		bin_n >>= 1
	return ans
(n, p) = map(int, input().split())
ans = 1
while ans < 10 ** 5 * 2 and (not n - p * ans >= ans >= get_n(n - p * ans)):
	ans += 1
if ans == 10 ** 5 * 2:
	print(-1)
else:
	print(ans)


import sys

def read():
	return sys.stdin.readline().strip()

def write(a):
	sys.stdout.write(a)

def check(n, p, m):
	a = n - p * m
	if a <= 0:
		return False
	b = bin(a)[2:][::-1]
	l = len(b)
	c = 0
	res = 0
	q = []
	for i in range(l):
		if b[i] == '1':
			q += [2 ** i]
			c += 1
			res += max(0, 2 ** (i - 1))
	d = c - m
	if d > 0:
		return False
	if d == 0:
		return True
	if res + d > 0:
		return True

def main():
	(n, p) = [int(i) for i in read().split()]
	ans = 10 ** 4
	for i in range(1, 10 ** 4 + 1):
		if check(n, p, i):
			ans = i
			break
	if ans == 10 ** 4:
		write('-1')
	else:
		write(str(ans))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 1000000007
INF = float('inf')

def lb(n):
	return n & (n ^ n - 1)

def main():
	(n, p) = RL()
	for i in range(1, 33):
		now = n - i * p
		if now >= i and bin(now).count('1') <= i:
			print(i)
			break
	else:
		print(-1)
main()


(n, p) = map(int, input().split())
ans = -1
for i in range(10001):
	if n - i * p >= i:
		c = bin(n - i * p)[2:].count('1')
		if c <= i:
			ans = i
			break
print(ans)


(N, P) = map(int, input().split())

def chk(k):
	x = N - k * P
	if x > 0 and sum(map(int, bin(x)[2:])) <= k <= x:
		return 1
	return 0
for i in range(1, 100):
	if chk(i):
		print(i)
		break
else:
	print(-1)


(n, p) = input('').split()
n = int(n)
p = int(p)
for i in range(1, 31):
	m = n
	m = m - i * p
	b = bin(m)
	str1 = str(b)
	count = str1.count('1', 0, len(str1))
	if m <= 0:
		print(-1)
		break
	elif count == i:
		print(i)
		break
	elif count < i:
		if m > i:
			print(i)
			break
		else:
			print(-1)
			break


(n, p) = map(int, input().split())
for k in range(41):
	m = n - k * p
	if m <= 0:
		print(-1)
		break
	s = bin(m)
	sumk = 0
	for i in range(len(s)):
		if s[-i - 1] == '1':
			sumk += 2 ** i
	if s.count('1') <= k <= sumk:
		print(k)
		break
else:
	print(-1)


(n, p) = map(int, input().split())
ok = False
for i in range(1, 32):
	current = n - i * p
	b = bin(current)[2:].count('1')
	if current >= i and b <= i:
		print(i)
		ok = True
		break
if not ok:
	print(-1)


(n, p) = map(int, input().split())
for i in range(100000):
	x = n - p * i
	bina = bin(x)[2:].count('1')
	if bina <= i and x >= i:
		print(i)
		exit()
print(-1)


(n, p) = map(int, input().split())
for k in range(1, 50):
	num = bin(n - k * p)
	if num.count('1') <= k <= n - k * p:
		print(k)
		exit()
print(-1)


import sys
import math
(n, p) = map(int, input().split())
for i in range(1, 1000000):
	if n - p * i >= i and bin(n - p * i)[2:].count('1') <= i:
		print(i)
		sys.exit()
print(-1)


(n, p) = [int(k) for k in input().split(' ')]

def cb(n):
	res = 0
	while n:
		if n % 2:
			res += 1
		n >>= 1
	return res
k = 0
res = -1
while n - k * p > 0:
	nbb = cb(n - k * p)
	if nbb <= k and n - k * p >= k:
		res = k
		break
	k += 1
print(res)


(n, p) = map(int, input().split())
i = 0
while True:
	if n - p * i < 0:
		print(-1)
		break
	if bin(n - p * i).count('1') <= i and i <= n - p * i:
		print(i)
		break
	i += 1


def dectobin(n, out):
	s = 0
	while n:
		s += n % 2
		n //= 2
	return s <= out
(n, p) = list(map(int, input().split()))
out = 0
f = 0
while n - p >= out + 1:
	n -= p
	out += 1
	if dectobin(n, out):
		f = 1
		break
if f == 1:
	print(out)
else:
	print(-1)


(a, b) = map(lambda x: int(x), input().split())
k = 0
s = 1
f = True
while k < s:
	a = a - b
	if a <= 0:
		break
	c = a
	k += 1
	s = 1
	while c != 1:
		s += c % 2
		c = c // 2
q = k - s
q1 = k
for i in range(q):
	a = a - b
	if a <= 0:
		break
	c = a
	k += 1
	s = 1
	while c != 1:
		s += c % 2
		c = c // 2
	if s == k:
		print(s)
		f = False
		break
if f and a > 0:
	print(q1)
if a <= 0:
	print(-1)


def f(n, p, k):
	n = n - k * p
	ans = 0
	l = 0
	z = []
	while n >= 1:
		ans += n % 2
		z.append(n % 2)
		n //= 2
	for i in range(len(z)):
		l += z[i] * 2 ** i
	if ans <= k <= l:
		return ans
	else:
		return 10 ** 4
(n, p) = map(int, input().split())
k = 10000
ans = 10 ** 4
for i in range(1, 10 ** 4):
	if f(n, p, i) != 10 ** 4:
		print(i)
		exit(0)
print(-1)


(n, p) = map(int, input().split())
power = []
power.append(1)
for i in range(1, 31):
	power.append(power[len(power) - 1] * 2)
ans = -1
i = 1
while i < 31:
	y = n - i * p
	if y <= 0 or y < i:
		break
	a = []
	while y:
		a.append(y % 2)
		y = y // 2
	count = 0
	for x in a:
		if x:
			count += 1
	if count <= i:
		ans = i
		break
	i += 1
print(ans)


def pro(g, v):
	if g == 0:
		if v == 0:
			return True
		else:
			return False
	y = 2 ** 100
	ans = 0
	x = g
	while x != 0:
		if x >= y:
			x -= y
			ans += 1
		y //= 2
	if ans <= v and v <= g:
		return True
	else:
		return False
(n, p) = map(int, input().split())
mini = 100000
for i in range(0, 40000):
	if n - p * i < 0:
		break
	x = pro(n - p * i, i)
	if x:
		mini = min(mini, i)
if mini == 100000:
	print(-1)
else:
	print(mini)


def check(n, p, m):
	a = n - p * m
	if a <= 0:
		return False
	b = bin(a)[2:][::-1]
	l = len(b)
	c = 0
	res = 0
	q = []
	for i in range(l):
		if b[i] == '1':
			q += [2 ** i]
			c += 1
			res += max(0, 2 ** (i - 1))
	d = c - m
	if d > 0:
		return False
	if d == 0:
		return True
	if res + d > 0:
		return True

def main():
	(n, p) = [int(i) for i in input().split()]
	ans = 10 ** 4
	for i in range(1, 10 ** 4 + 1):
		if check(n, p, i):
			ans = i
			break
	if ans == 10 ** 4:
		print(-1)
	else:
		print(ans)
main()


import math
(n, p) = map(int, input().split())
ans = 0
while 1:
	ans += 1
	n -= p
	if n <= 0:
		print(-1)
		exit(0)
	if bin(n)[2:].count('1') <= ans and n >= ans:
		break
print(ans)


def get_n(n, k):
	if bin(n).count('1') > k or k > n:
		return False
	return True
(n, p) = list(map(int, input().split()))
if p - n >= 0:
	print(-1)
elif p - n == -1:
	print(1)
else:
	for i in range(1, 10101):
		if get_n(n - p * i, i):
			print(i)
			return
	print(-1)


import sys as _sys

def main():
	(n, p) = _read_ints()
	try:
		result = find_min_terms_n(n, p)
	except ValueError:
		result = -1
	print(result)

def _read_line():
	result = _sys.stdin.readline()
	assert result[-1] == '\n'
	return result[:-1]

def _read_ints():
	return map(int, _read_line().split())

def find_min_terms_n(n, p):
	for m in range(1, 32 + 1):
		necessary_n = n - m * p
		if necessary_n < 0:
			continue
		x = necessary_n
		active_bits_n = 0
		while x:
			active_bits_n += x & 1
			x >>= 1
		if m < active_bits_n:
			continue
		if m > necessary_n:
			continue
		return m
	raise ValueError
main()


(n, p) = map(int, input().split())
if p == 0:
	dv = str(bin(n))[2:]
	colvo = dv.count('1')
	print(colvo)
else:
	m = 1
	while n - m * p >= 0:
		a = n - m * p
		dv = str(bin(a))[2:]
		colvo = dv.count('1')
		if colvo <= m and m <= a:
			print(m)
			exit(0)
		m += 1
	print(-1)


(n, p) = map(int, input().split())
ans = -1
for k in range(1, 31):
	if n - k * p >= k:
		if bin(n - k * p).count('1') <= k:
			ans = k
			break
print(ans)


def ones(n):
	cnt = 0
	while n > 0:
		cnt += n % 2
		n >>= 1
	return cnt
(n, p) = map(int, input().split())
least = -1
for i in range(1, 40):
	pbinar = n - i * p
	if pbinar < 0:
		break
	pone = ones(pbinar)
	if pone <= i <= pbinar:
		least = i
		break
print(least if least != -1 else -1)


(n, p) = map(int, input().split())
for i in range(31):
	t = n - i * p
	c = bin(t).count('1')
	if c <= i and t >= i:
		print(i)
		exit(0)
print(-1)


import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 10000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def read():
	tc = 1
	if tc:
		input = sys.stdin.readline
	else:
		sys.stdin = open('input1.txt', 'r')
		sys.stdout = open('output1.txt', 'w')

def solve():
	(n, p) = mi()
	ans = -1
	ans = -1
	l = 1
	r = 1005
	for i in range(1, 1005):
		x = n - p * i
		s = list(bin(x)[2:])
		if i <= x and i >= s.count('1'):
			ans = i
			break
	print(ans)
read()
solve()


(n, p) = map(int, input().split())
for k in range(1, 31):
	if n - k * p >= k and bin(n - k * p).count('1') <= k:
		print(k)
		exit()
print('-1')


def solve():
	(n, p) = map(int, input().split())
	for i in range(1, 32):
		if n - i * p >= i and bin(n - i * p).count('1') <= i:
			return i
	return -1
print(solve())


(n, p) = list(map(int, input().split()))
ans = 1
n2 = n
while n2 > 0:
	n2 = n - ans * p
	count1 = bin(n2).count('1', 2)
	if count1 <= ans and ans <= n2:
		print(ans)
		break
	ans += 1
else:
	print(-1)


(n, p) = map(int, input().split())
f = 0
for i in range(1, 31):
	x = n - i * p
	b = bin(x)
	if x < 0:
		b = b[3:]
	else:
		b = b[2:]
	if x >= i:
		ones = 0
		for j in range(len(b)):
			if b[j] == '1':
				ones += 1
		if ones <= i:
			f = 1
			print(i)
			break
if f == 0:
	print(-1)


def check(k, n, p):
	t = n - p * k
	s = bin(t)[2:]
	count = 0
	for i in range(len(s)):
		if s[i] == '1':
			count += 1
	return count <= k and t >= k

def main():
	(n, p) = map(int, input().split())
	i = 1
	while i < 10000:
		if check(i, n, p):
			print(i)
			return
		i += 1
	print(-1)
main()


[n, m] = list(map(int, input().split()))

def cnt(x):
	y = bin(x)
	y = y[2:]
	return y.count('1')
ans = 1
for i in range(1, 32):
	if n - i * m >= i and cnt(n - i * m) <= i:
		print(i)
		ans = 0
		break
if ans:
	print(-1)


def ones(n):
	result = 0
	while n > 0:
		n = n & n - 1
		result = result + 1
	return result

def can(n, p, cnt):
	nn = n - p * cnt
	if nn < cnt:
		return False
	if ones(nn) > cnt:
		return False
	return True

def solve(n, p):
	i = 1
	while i * p <= n:
		if can(n, p, i):
			return i
		i = i + 1
	return -1

def main():
	(n, p) = [int(s) for s in input().split()]
	answer = solve(n, p)
	print(answer)
main()


from math import log2
(n, p) = list(map(int, input().split()))
f = n
ans = 10 ** 9
j = 0
for __ in range(1000):
	n = f
	i = 0
	num = 0
	n -= p * j
	if n <= 0:
		break
	x = 2 ** int(log2(n))
	while n >= 0:
		if n - x >= 0:
			n -= x
			num += 1
			i += 1
		x //= 2
		if n == 0:
			break
	if f - p * j < j:
		pass
	elif j >= i and n == 0:
		ans = min(ans, num + j - i)
	j += 1
if ans == 10 ** 9:
	print(-1)
else:
	print(ans)


(n, p) = map(int, input().split())
for i in range(1, 1000):
	x = n - i * p
	b = bin(x)
	if x <= 0:
		break
	if b.count('1') <= i <= x:
		print(i)
		exit()
print(-1)


def f(n, j):
	k = 0
	while n > 0 and k <= j:
		m = 1
		while m <= n:
			m *= 2
		n -= m // 2
		k += 1
	if k <= j:
		return k
	return -1
mini = 10 ** 9
ans = -1
(n, p) = map(int, input().split())
for i in range(1, 10 ** 9):
	if n - p * i > 0:
		if n - p * i < i:
			print(-1)
			break
		else:
			b = f(n - p * i, i)
			if b != -1:
				print(i)
				break
	else:
		print(-1)
		break


def get(n, k):
	return n >> k & 1

def cal(n):
	sum = 0
	for i in range(30):
		sum += get(n, i)
	return sum
(n, k) = map(int, input().split())
rs = -1
for i in range(30):
	X = n - i * k
	if cal(X) <= i and X >= i:
		rs = i
		break
print(rs)


(n, p) = map(int, input().split())
out = 1
while n:
	n -= p
	if n < out:
		print(-1)
		break
	s = bin(n)
	if s.count('1') <= out:
		print(out)
		break
	out += 1


def count1(n):
	return bin(n).count('1')
(n, p) = map(int, input().split())
if p == 0:
	print(count1(n))
else:
	for k in range(1, 10 ** 8):
		n1 = n - k * p
		if n1 <= 0:
			print(-1)
			break
		k1 = count1(n1)
		if k1 == k:
			print(k)
			break
		elif 0 < k - k1 <= n1 - k1:
			print(k)
			break


(a, b) = map(int, input().split())

def bn(x):
	m = 0
	while x > 0:
		m += x % 2
		x //= 2
	return m
mn = 100000000
idx = 0
if b == 0:
	print(bn(a))
	exit(0)
else:
	for n in range(1, 100):
		j = n * b
		if a <= j:
			break
		elif bn(a - j) <= n and a - j >= n:
			print(n)
			exit(0)
print(-1)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, p) = ria()
		mi = 9999999999999999999999999999999
		c = 0
		for k in range(1, 40):
			if n - k * p >= k:
				s = str(bin(n - k * p))[2:]
				if s.count('1') <= k:
					print(k)
					c = 1
					break
		if c == 0:
			print(-1)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


(n, k) = map(int, input().split())
f = 0
c = 0
for i in range(35):
	d = n
	c = 0
	d = n - i * k
	t = d
	while d > 0:
		c += d % 2
		d //= 2
	if c <= i and i <= t:
		f = 1
		print(i)
		break
if f == 0:
	print(-1)


import time
(n, p) = map(int, input().split())
nt = time.time()
for i in range(1, 10000, 1):
	if n - p * i < i:
		break
	now = bin(n - p * i)[2:].count('1')
	if now <= i and now != 0:
		print(i)
		exit(0)
print(-1)


(n, p) = map(int, input().split())
count = 100
if n - p == 0:
	print(-1)
	exit(0)
k = 0
while k <= 32:
	if n - p * k >= k:
		temp = bin(n - p * k)
		c = str(temp)[2:].count('1')
		if c <= k and c != 0:
			print(k)
			break
	k += 1
else:
	print(-1)


(n, p) = map(int, input().split())
k = 1
while n - p * k > 0:
	count = 0
	temp = n - p * k
	while temp > 0:
		if temp & 1:
			count += 1
		temp = temp >> 1
	if count <= k:
		break
	k += 1
if n - p * k >= k:
	print(k)
else:
	print(-1)


import bisect
(n, p) = map(int, input().split())
P = [1 << i for i in range(81)]
for ans in range(1000):
	x = n - ans * p
	zz = x
	if x <= 0:
		print(-1)
		break
	count = 0
	while x != 0:
		y = bisect.bisect_right(P, x)
		x -= P[y - 1]
		count += 1
	if ans >= count and zz >= ans:
		print(ans)
		break


(n, p) = [int(i) for i in input().split()]

def g(x: int, k: int) -> list:
	q = bin(x)[2:][::-1]
	(r1, r2, r3, r) = ([], [], [], [])
	s = sum(map(int, list(q)))
	i = len(q) - 1
	while s < k:
		qq = int(q[i]) * 2 + int(q[i - 1])
		ost = ''
		if len(q[i:]) > 1:
			ost = '0' + q[i + 1:]
		s = sum(map(int, list(q[:i - 1] + ost)))
		input(f'\t(до) q = {q}\n\ti = {i}, s = {s}, qq = {qq}\n')
		if s + qq > k:
			i -= 1
			continue
		q = q[:i - 1] + str(qq) + ost
		i -= 1
		s = sum(map(int, list(q)))
		input(f'\t(после) q = {q}\n\ti = {i}, s = {s}, qq = {qq}\n')
	for i in range(len(q)):
		j = int(q[i])
		if j >= 1:
			r += [f'2^{i}'] * j
			r1.append(f"{['', f'{j}*'][j > 1]}" + f'2^{i}')
			r2.append(f"{['', f'{j}*'][j > 1]}" + f'{2 ** i}')
			r3.append(f'{j * 2 ** i}')
	return (r[::-1], r1, r2, r3)
if n < 0 or (n == 0 and p == 0):
	exit('-1')
if p == 0:
	print(bin(n).count('1'))
else:
	b = n
	k = -1
	z = p / abs(p)
	if n - p >= 1:
		while (b + k * p) * z > n * z or k == -1:
			b -= p
			b2 = bin(b)[2:]
			k = b2.count('1')
		k = (n - b) // p
		if b >= k:
			print(k)
		else:
			print(-1)
	else:
		print(-1)


BitsSetTable256 = [0] * 256

def initialize():
	BitsSetTable256[0] = 0
	for i in range(256):
		BitsSetTable256[i] = (i & 1) + BitsSetTable256[i // 2]
initialize()

def countSetBits(n):
	return BitsSetTable256[n & 255] + BitsSetTable256[n >> 8 & 255] + BitsSetTable256[n >> 16 & 255] + BitsSetTable256[n >> 24]
(n, p) = map(int, input().split())
if n < 1 + p:
	print(-1)
else:
	allowed = 0
	while 1:
		n += -p
		allowed += 1
		if n < 2 ** allowed - 1:
			print(-1)
			break
		if countSetBits(n) <= allowed:
			print(allowed)
			break


(n, p) = map(int, input().split())

def countSetBits(num):
	binary = bin(num)
	if num < 0:
		binary = binary[1:]
	setBits = [ones for ones in binary[2:] if ones == '1']
	return len(setBits)
found = False
for i in range(1, 33):
	if n - i * p >= i and countSetBits(n - i * p) <= i:
		found = True
		print(i)
		break
if not found:
	print(-1)


def bin(x):
	return '{0:b}'.format(x)
(n, p) = [int(i) for i in input().split()]
nA = True
k = 1
while k < 33:
	if k == 32:
		print(-1)
	else:
		t = bin(n - k * p)
		a = t.count('1')
		if a <= k and a > 0 and (n >= k * (p + 1)):
			print(k)
			break
	k += 1


import sys

def one_count(x):
	return bin(x).count('1')

def solve(n, p):
	for k in range(0, 33):
		y = n - k * p
		one_count_y = one_count(y)
		if y >= k and one_count_y <= k:
			return k
	return -1
solve(101, 50)

def pp(input):
	print(solve(*map(int, input().strip().split(' '))))
if 'pydev' in sys.argv[0]:
	from string_source import string_source, codeforces_parse
	x = 'inputCopy\n24 0\noutputCopy\n2\ninputCopy\n24 1\noutputCopy\n3\ninputCopy\n24 -1\noutputCopy\n4\ninputCopy\n4 -7\noutputCopy\n2\ninputCopy\n1 1\noutputCopy\n-1'
	for (q, a) in codeforces_parse(x):
		pp(string_source(q))
		print(a)
		print('----')
else:
	pp(sys.stdin.readline)


(n, p) = map(int, input().split())
m = 10000000000
q = 0
for i in range(1, 100):
	a = n - i * p
	if a > 0:
		u = a
		o = 0
		while u > 0:
			if u % 2 == 1:
				o += 1
				u //= 2
			else:
				u //= 2
		mi = o
		if i >= mi and a >= i:
			print(i)
			q = 1
			break
	else:
		break
if q == 0:
	print(-1)


(n, p) = map(int, input().split())

def term_counter(n, counter):
	if n == 1:
		return counter + 1
	if n % 2 == 1:
		n -= 1
		counter += 1
		return term_counter(n, counter)
	else:
		while n != 1 and n % 2 != 1:
			n = int(n / 2)
		if n == 1:
			return counter + 1
		else:
			n -= 1
			counter += 1
			return term_counter(n, counter)
i = 1
done = False
while n - p * i > 0:
	if term_counter(n - p * i, 0) <= i:
		if n - p * i >= i:
			print(i)
			done = True
			break
		else:
			i += 1
			continue
	else:
		i += 1
		continue
if not done:
	print(-1)


def decimal_to_binary(x):
	res = []
	while x > 0:
		res.append(x % 2)
		x //= 2
	return res[::-1]
(n, p) = list(map(int, input().split()))
for k in range(50):
	x = n - k * p
	if x < 0:
		break
	res = decimal_to_binary(x).count(1)
	if res <= k and res > 0 and (n - k * p >= k):
		print(k)
		exit(0)
print(-1)


import sys

def get_one(n):
	cnt = 0
	while n > 0:
		if n % 2 == 1:
			cnt += 1
		n //= 2
	return cnt
(n, p) = map(int, input().split())
for i in range(10000):
	if n > i * p and get_one(n - i * p) <= i <= n - i * p:
		print(i)
		sys.exit()
print(-1)


def cnt(n, a):
	count = 0
	p = 1
	while n:
		count += (n & 1) * p
		if a:
			p *= 2
		n >>= 1
	return count

def main():
	(n, p) = map(int, input().split())
	s = 1 if p < 0 else -1
	ans = 10000000000
	cop = n
	if p == 0:
		print(cnt(n, False))
		return
	p = abs(p)
	i = -1
	while i < 64:
		i += 1
		if cnt(n, True) >= abs(cop - n) // p and cnt(n, False) <= abs(cop - n) // p:
			ans = min(ans, abs(cop - n) // p)
		n += s * p
		if n < 0:
			break
	print(-1 if ans == 10000000000 else ans)
main()


(n, p) = map(int, input().split())
ans = 1
fl = False
if n == p:
	print(-1)
else:
	while n - p * ans >= 0:
		b = bin(n - p * ans)[2:].count('1')
		if b <= ans <= n - p * ans:
			fl = True
			break
		ans += 1
	if fl:
		print(ans)
	else:
		print(-1)


(n, p) = map(int, input().split())
ones = '{0:b}'.format(n).count('1')
t = 0
while (ones > t or n < t) and n > 0:
	n -= p
	t += 1
	ones = '{0:b}'.format(n).count('1')
if n <= 0:
	print(-1)
else:
	print(t)


(n, p) = map(int, input().split())
if n == 0:
	print(0)
elif p >= n:
	print(-1)
else:
	i = 0
	while 1:
		n -= p
		if n <= 0:
			print(-1)
			break
		i += 1
		s = str(bin(n))
		k = 0
		for j in s:
			if j == '1':
				k += 1
		if k <= i and n >= i:
			print(i)
			break


(n, p) = map(int, input().split())
ans = -1
for i in range(40):
	t = n - p * i
	if t < 0:
		break
	cnt = 0
	while t:
		if t & 1:
			cnt += 1
		t >>= 1
	if n - p * i >= i and cnt <= i:
		print(i)
		exit()
print(ans)


def kol(a):
	if a <= 0:
		return -1
	elif a == 1:
		return 1
	elif a % 2 == 1:
		return kol(a // 2) + 1
	else:
		return kol(a // 2)
(n, p) = map(int, input().split())
prov = False
for i in range(1, 1000):
	z = kol(n - i * p)
	if z != -1 and z <= i and (n - i * p >= i):
		prov = True
		break
if prov:
	print(i)
else:
	print(-1)


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def count1(s):
	c = 0
	for i in s:
		if i == '1':
			c += 1
	return c

def Binary(n):
	return bin(n).replace('0b', '')

def Decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True
(n, p) = map(int, input().split())
f = False
for i in range(1, 36):
	t = n - i * p
	if t >= i:
		s = Binary(t)
		c = count1(s)
		if c <= i:
			f = True
			ans = i
			break
	else:
		break
if f:
	print(ans)
else:
	print(-1)


(x, p) = map(int, input().split())
ans = float('inf')
for i in range(0, 100001):
	y = x - i * p
	if y <= 0:
		continue
	aaa = 0
	for (j, el) in enumerate(reversed(bin(y))):
		if el == '1':
			aaa += 2 ** j
			if aaa >= i:
				break
	bbb = bin(y).count('1')
	if bbb <= i <= aaa:
		ans = min(ans, i)
if ans == float('inf'):
	ans = -1
print(ans)


def countSetBits(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count
t = 1
for _ in range(t):
	(n, p) = map(int, input().split())
	count = 0
	found = False
	while n > 0 and (not found) and (count < 32):
		n -= p
		count += 1
		if n < 0:
			break
		x = countSetBits(n)
		if x <= count and n >= count:
			found = True
	if found:
		print(count)
	else:
		print(-1)


(n, p) = map(int, input().split())
answer = 1
while True:
	n -= p
	if n < answer:
		print(-1)
		break
	if bin(n).count('1') <= answer:
		print(answer)
		break
	answer += 1


import math as mt
import sys, string
input = sys.stdin.readline
from collections import defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
(n, p) = M()
if p == 0:
	if n >= 0:
		print(bin(n)[2:].count('1'))
	else:
		print(-1)
if p >= n:
	print(-1)
else:
	for i in range(-1000, 1001):
		if p == 0:
			continue
		if i >= bin(n - i * p)[2:].count('1') and bin(n - i * p)[2:].count('1') > 0:
			if n - i * p > 0:
				if i <= n - i * p:
					print(i)
					break
				else:
					print(-1)
					break
			else:
				print(-1)
				break


def solve():
	(n, p) = map(int, input().split())
	for k in range(1, 32):
		n1 = n - k * p
		if n1 < k:
			continue
		b = 0
		while n1 > 0:
			b += n1 % 2
			n1 //= 2
		if b <= k:
			print(k)
			return
	print(-1)
solve()


(n, p) = map(int, input().split())
min_ans = -1
for i in range(1, 10000):
	nn = n
	nn -= i * p
	if nn > 0:
		st = bin(nn)[2:]
		if st.count('1') <= i and nn >= i:
			min_ans = i
			break
print(min_ans)


inputs = [int(x) for x in input().split()]
n = inputs[0]
y = inputs[1]
pos = False
for i in range(1000000100):
	if n - i * y < i:
		break
	if bin(n - i * y).count('1') <= i:
		print(i)
		pos = True
		break
if pos == False:
	print(-1)


def min_summies(n, p):
	for k in range(1, 50):
		num = bin(n - k * p)
		if num.count('1') <= k <= n - k * p:
			return k
	return -1
(n, p) = map(int, input().split())
print(min_summies(n, p))


(n, p) = list(map(int, input().split()))
k = 1
z = []
while len(bin(n - k * p)) - 2 >= k and n - k * p > 0:
	if bin(n - k * p).count('1') <= k:
		z.append(k)
	k += 1
if len(z) > 0:
	print(min(z))
else:
	print(-1)


import sys
input = sys.stdin.readline
from bisect import bisect_left
from bisect import bisect_right
from math import ceil, factorial

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
(n, p) = int_array()
ans = INF
for i in range(1, 100):
	x = n - i * p
	if x < 0:
		break
	bcs = bin(x).replace('0b', '').count('1')
	if i >= bcs and i <= x:
		ans = min(ans, i)
if ans == INF:
	ans = -1
print(ans)


import sys
import collections
import heapq
input = sys.stdin.readline

def rints():
	return map(int, input().strip().split())

def rstr():
	return input().strip()

def rint():
	return int(input().strip())

def rintas():
	return [int(i) for i in input().strip().split()]

def gcd(a, b):
	if a == 0:
		return b
	return gcd(a % b, a)
(n, p) = rints()
i = 1
n -= p
while n > 0:
	b = bin(n)
	if n >= i >= b.count('1'):
		print(i)
		exit()
	i += 1
	n -= p
print(-1)


(n, p) = map(int, input().split())
aws = 1
while True:
	min_number = aws * (2 ** 0 + p)
	if min_number > n:
		aws = -1
		break
	elif min_number == n:
		break
	elif bin(n - aws * p).count('1') <= aws:
		break
	aws += 1
print(aws)


(n, p) = map(int, input().split())
ans = 10 ** 18
for k in range(10 ** 5 + 1):
	x = n - k * p
	if x < 0:
		break
	s = str(bin(x)[2:])
	l = 0
	r = 0
	for i in range(len(s))[::-1]:
		if s[i] == '1':
			l += 1
			r += 2 ** (len(s) - 1 - i)
	if l <= k <= r:
		ans = min(ans, k)
		break
if ans == 10 ** 18:
	print(-1)
else:
	print(ans)


from sys import stdin, stdout
from math import gcd
input = stdin.readline
(n, p) = map(int, input().split())
for k in range(32):
	if n - k * p >= k and bin(n - k * p).count('1') <= k:
		print(k)
		break
else:
	print(-1)


def bitcount(n):
	count = 0
	while n > 0:
		count = count + 1
		n = n & n - 1
	return count
(n, p) = input('').split()
n = int(n)
p = int(p)
for i in range(1, 31):
	m = n
	m = m - i * p
	count = bitcount(m)
	if m <= 0:
		print(-1)
		break
	elif count == i:
		print(i)
		break
	elif count < i:
		if m > i:
			print(i)
			break
		else:
			print(-1)
			break


(n, p) = map(int, input().split())
n -= p
f = False
for i in range(100):
	s = bin(n)
	if len(s) - 2 >= i + 1 >= s.count('1') > 0 and n > 0:
		k = i + 1
		f = True
		break
	else:
		n -= p
if f:
	print(k)
else:
	print(-1)


import sys
input = sys.stdin.readline
from math import *
(n, p) = map(int, input().split())
c = 0
if p == 0:
	print(bin(n).count('1'))
	exit(0)
while n > 0:
	m = n - c * p
	if m < 0:
		print(-1)
		exit(0)
	l = list(bin(m))[2:]
	l = l[::-1]
	s = 0
	for j in range(len(l)):
		if l[j] == '1':
			s += j
	if l.count('1') <= c <= s or (c == 1 and m == 1):
		print(c)
		exit(0)
	c += 1


(n, k) = map(int, input().split())
i = 1
n -= k
while n > 0 and (not bin(n).count('1') <= i <= n):
	n -= k
	i += 1
if n > 0:
	print(i)
else:
	print(-1)


inp = input().split()
n = int(inp[0])
p = int(inp[1])
flag = 0
for i in range(100):
	if n - i * p < i:
		break
	if bin(n - i * p).count('1') <= i:
		print(i)
		flag = 1
		break
if flag == 0:
	print(-1)


(n, p) = map(int, input().split())
if n <= p:
	print(-1)
	exit()
for ans in range(1, 10 ** 6):
	x = n - p * ans
	if x >= ans and bin(x).count('1') <= ans:
		print(ans)
		break
else:
	print(-1)


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	(n, p) = geti()
	for i in range(1, 32):
		if n - i * p >= i and bin(n - i * p).count('1') <= i:
			return i
	return -1
print(solve())


def bit_count(A, i):
	answ = 0
	j = 0
	d = []
	while A > 0:
		if A & 1:
			answ += 1
		A >>= 1
		d.append(j)
		j += 1
	if answ > 0:
		while answ < i and d:
			if d[-1] > 1:
				answ += 1
				nj = d.pop()
				d.append(nj)
				d.append(nj)
			elif d[-1] == 1:
				answ += 1
				d.pop()
			else:
				d.pop()
	return answ
(n, p) = map(int, input().split())
i = 0
while bit_count(n - p * i, i) != i and i < 5757:
	i += 1
if i < 5757:
	print(i)
else:
	print(-1)


(n, p) = map(int, input().split())

def count(s):
	c = 0
	b = list(bin(s))
	b.pop(0)
	b.pop(0)
	for i in b:
		if i == '1':
			c += 1
	return c
i = 1
if p > 0:
	l = n / (p + 1)
	while i <= l:
		if count(n - i * p) <= i:
			print(i)
			break
		else:
			i += 1
	else:
		print('-1')
else:
	i = 1
	while True:
		if count(n - i * p) <= i:
			print(i)
			break
		else:
			i += 1