Число называется сильным, если оно является степенью двойки или факториалом. Другими словами, число \(m\) сильное, если существует неотрицательное целое число \(d\) такое, что \(m=2^d\) или \(m=d!\), где \(d!=1\cdot 2\cdot \ldots \cdot d\) (в частности, \(0! = 1\)). Например, \(1\), \(4\) и \(6\) являются сильными, потому что \(1=1!\), \(4=2^2\), \(6=3!\), а \(7\), \(10\) или \(18\) не являются.
Вам дано положительное число \(n\). Найдите минимальное число \(k\) такое, что \(n\) можно представить в виде суммы \(k\) различных сильных чисел, или определите, что такого \(k\) не существует.
Выходные данные
Для каждого набора входных данных выведите ответ на отдельной строке.
Если \(n\) не может быть представлено как сумма различных сильных чисел, выведите \(-1\).
Иначе выведите одно положительное число — минимально возможное число \(k\).
Примечание
В первом примере \(7\) может быть представлена как \(7=1+6\), где \(1\) и \(6\) являются сильными. Так как \(7\) не является сильным числом, мы знаем, что минимальное значение \(k\) в этом случае \(k=2\).
Во втором примере один из способов разложить \(11\) в сумму трех сильных чисел такой: \(11=1+4+6\). Можно показать, что нельзя представить \(11\) в виде суммы двух или менее сильных чисел.
В третьем примере \(240\) может быть представлено как \(240=24+32+64+120\). Обратите внимание, что \(240=120+120\) не является корректным представлением, т. к. сильные числа должны быть различны.
В четвертом примере \(17179869184=2^{34}\), поэтому \(17179869184\) является сильным числом, и минимальное \(k\) в этом случае \(k=1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
11
240
17179869184
|
2
3
4
1
|