n = 0  # натуральное число N (1 <= N <= 109)
p = 0  # основание системы счисления p (2 <= p <= 16)

# получение входных данных из файла in.txt
with open('in.txt', 'r') as f:
    line = f.readline()
    n = int(line.split(' ')[0])
    p = int(line.split(' ')[1])


newNum = ''  # число в другой системе исчисления
ones = 0  # количество единиц

# перевод числа в другую систему исчисления
while n > 0:
    newNum = str(n % p) + newNum
    n //= p

# подсчет количества единиц
ones = newNum.count('1')

# запись выходных данных в файл out.txt
with open('out.txt', 'w') as f:
    f.write(str(ones))