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: interview

Starter code:

Solutions:
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)


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)

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)


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)


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

#24 0
#24 1
#24 -1
#4 -7
#1 1
#5 2


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)

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,p=list(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:
        # print(m)
        a=n-m*p
        dv=str(bin(a))[2:]
        colvo=dv.count("1")
        if colvo<=m and m<=a:
            print(m)
            return
        m+=1
    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, 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)

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)


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 = 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 sys
import math
# sys.stdin = open("in.txt")
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)
        return
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)

n, p = map(int, input().split())
if n == 0:
    print(0)
else:
    if 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

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

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, p = list(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
        else:
            if 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)


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 bn(x):
    b = []
    i = 1
    j = 0
    while j < 32:
        #print(x & i, x, i)
        b.append(int(x & i != 0))
        i = i << 1
        j += 1
    b.reverse()
    return sum(b)


n, p = list(map(int, input().split()))
for i in range(1, 32):
    bi = bn(n - i * p)
    if bi <= i <= n - i * p:
        print(i)
        return
print(-1)
    
    


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)

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 = list(map(int, input().split()))
mini = 100000
for i in range(0, 40000):
	if n - p * i < 0:
		break
	x = pro(n - p * i, i)
	#print (x, i)
	if (x):
		#print ("YES")
		mini = min(mini, i)
if mini == 100000:
	print(-1)
else:
	print (mini)


import math
x, y = list(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)