C. Факториалы и степени двойки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Число называется сильным, если оно является степенью двойки или факториалом. Другими словами, число $$$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$$$ не существует.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Описание одного набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 10^{12}$$$).

Выходные данные

Для каждого набора входных данных выведите ответ на отдельной строке.

Если $$$n$$$ не может быть представлено как сумма различных сильных чисел, выведите $$$-1$$$.

Иначе выведите одно положительное число — минимально возможное число $$$k$$$.

Пример
Входные данные
4
7
11
240
17179869184
Выходные данные
2
3
4
1
Примечание

В первом примере $$$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$$$.