题目描述

如果一个数是 $2$ 的幂或阶乘，则称其为“强大数”。换句话说，如果存在非负整数 $d$，使得 $m=2^d$ 或 $m=d!$，那么数 $m$ 就是强大数（其中 $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$，请输出 $-1$。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

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

输出格式

对于每组测试用例，输出一行答案。

如果 $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$。

由 ChatGPT 4.1 翻译

样例

4
7
11
240
17179869184

2
3
4
1