CF1646C.Factorials and Powers of Two

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$.

一个数被称为“强数”，如果它是 2 的幂或一个阶乘数。换言之，若存在一个非负整数 $d$，使得 $m = 2^d$ 或 $m = d!$（其中 $d! = 1 \cdot 2 \cdot \ldots \cdot d$；特别地，$0! = 1$），则称该数 $m$ 为强数。例如，$1$、$4$ 和 $6$ 是强数，因为 $1 = 1!$，$4 = 2^2$，且 $6 = 3!$；但 $7$、$10$ 和 $18$ 不是强数。

给定一个正整数 $n$，求最小的整数 $k$，使得 $n$ 可表示为 $k$ 个互不相同的强数之和；若不存在这样的 $k$，请说明这一点。

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}$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是测试用例的描述。

每个测试用例仅由一行组成，包含一个整数 $n$（$1\le n\le 10^{12}$）。

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$.

对于每个测试用例，请在单独的一行上输出答案。

如果 $n$ 无法表示为若干互不相同的强数（powerful numbers）之和，则输出 $-1$。

否则，输出一个正整数——即满足条件的最小可能的 $k$ 值。

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$.

在第一个测试用例中，$7$ 可以表示为 $7=1+6$，其中 $1$ 和 $6$ 均为“强数”（powerful number）。由于 $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$。