Factorials and Powers of Two
Contest: Codeforces Round 774 (Div. 2)
Difficulty rating: 1500
Tags: bitmasks, brute force, constructive algorithms, dp, math

A number is called powerful if it is a power of two or a factorial. In other words, the number $$$m$$$ is powerful if there exists a non-negative integer $$$d$$$ such that $$$m=2^d$$$ or $$$m=d!$$$, where $$$d!=1\cdot 2\cdot \ldots \cdot d$$$ (in particular, $$$0! = 1$$$). For example $$$1$$$, $$$4$$$, and $$$6$$$ are powerful numbers, because $$$1=1!$$$, $$$4=2^2$$$, and $$$6=3!$$$ but $$$7$$$, $$$10$$$, or $$$18$$$ are not.

You are given a positive integer $$$n$$$. Find the minimum number $$$k$$$ such that $$$n$$$ can be represented as the sum of $$$k$$$ distinct powerful numbers, or say that there is no such $$$k$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

A test case consists of only one line, containing one integer $$$n$$$ ($$$1\le n\le 10^{12}$$$).

Output format:
For each test case print the answer on a separate line.

If $$$n$$$ can not be represented as the sum of distinct powerful numbers, print $$$-1$$$.

Otherwise, print a single positive integer  — the minimum possible value of $$$k$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$7$$$ can be represented as $$$7=1+6$$$, where $$$1$$$ and $$$6$$$ are powerful numbers. Because $$$7$$$ is not a powerful number, we know that the minimum possible value of $$$k$$$ in this case is $$$k=2$$$.

In the second test case, a possible way to represent $$$11$$$ as the sum of three powerful numbers is $$$11=1+4+6$$$. We can show that there is no way to represent $$$11$$$ as the sum of two or less powerful numbers.

In the third test case, $$$240$$$ can be represented as $$$240=24+32+64+120$$$. Observe that $$$240=120+120$$$ is not a valid representation, because the powerful numbers have to be distinct.

In the fourth test case, $$$17179869184=2^{34}$$$, so $$$17179869184$$$ is a powerful number and the minimum $$$k$$$ in this case is $$$k=1$$$.

Example input:
4
7
11
240
17179869184

Example output:
2
3
4
1

Editorial:
If the problem asked to represent $$$n$$$ as a sum of distinct powers of two only (without the factorials), then there is a unique way to do it, using the binary representation of $$$n$$$ and the number of terms will be the number of digits equal to $$$1$$$ in this binary representation. Let's denote this number by $$$\text{ones}(n)$$$.
If we fix the factorials we are going to use in the sum, then the rest of the terms are uniquely determined because of the observation above. Note that $$$1$$$ and $$$2$$$ will not be considered as factorials in order to avoid repeating terms.
So, to solve the problem it is enough to iterate through all possibilities of including or not including each factorial (up to $$$14!$$$) and for each of them calculate the number of terms used in the sum. If we used $$$f$$$ factorials and their sum is $$$s$$$, then the number of terms can be calculated as $$$f+\text{ones}(n-s)$$$. The minimum of all these numbers will be the answer.
Intended complexity: $$$\mathcal{O}(2^k)$$$ where $$$k$$$ is the biggest positive integer such that $$$k!\leq n$$$