Васе нравятся любые числа, лишь бы они были целыми степенями двойки. Петя, в отличие от Васи, более консервативен, и ему нравится только одно число \(p\) (оно может быть положительным, отрицательным или нулём). Они решили объединить свои вкусы и изобрели \(p\)-двоичные числа вида \(2^x + p\), где \(x\) — неотрицательное целое число.
Например, некоторые \(-9\)-двоичные («минус девять» двоичные) числа — это \(-8\) (минус восемь), \(7\) и \(1015\) (\(-8=2^0-9\), \(7=2^4-9\), \(1015=2^{10}-9\)).
Теперь ребята используют \(p\)-двоичные числа, чтобы представлять всё вокруг. Они столкнулись с проблемой: для данного положительного целого \(n\), какое наименьшее количество \(p\)-двоичных чисел (не обязательно различных) им понадобится, чтобы представить \(n\) в виде их суммы? Возможно, что представления вообще не существует. Помогите им справиться с этой задачей.
Например, при \(p=0\) число \(7\) можно представить как \(2^0 + 2^1 + 2^2\).
А при \(p=-9\) число \(7\) можно представить одним числом \((2^4-9)\).
Обратите внимание, что отрицательные \(p\)-двоичные числа разрешается использовать в сумме (пример есть в секции Примечание).
Выходные данные
Если \(n\) нельзя представить как сумму какого угодно количества \(p\)-двоичных чисел, выведите одно число \(-1\). В противном случае, выведите минимальное число слагаемых.
Примечание
\(0\)-двоичные числа — это обычные степени двойки, поэтому в первом примере мы можем представить \(24 = (2^4 + 0) + (2^3 + 0)\).
Во втором примере мы можем представить \(24 = (2^4 + 1) + (2^2 + 1) + (2^0 + 1)\).
В третьем примере мы можем представить \(24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)\). Обратите внимание, что одинаковые слагаемые разрешены.
В четвёртом примере мы можем представить \(4 = (2^4 - 7) + (2^1 - 7)\). Обратите внимание, что второе слагаемое отрицательное, и это разрешено.
В пятом примере ни одного представления не существует.