3650. Powerful数

【题目描述】

如果一个数是 2 的次幂或是一个阶乘数，那么这个数被称为 Powerful 数。换句话说，如果对于一个数 $m$，存在一个非负整数 $d$，使得 $m = 2^d$ 或 $m = d!$，那么这个数 $m$ 是一个 Powerful 数

给定一个正整数 $n$，请找到一个最小的数 $k$，使得 $n$ 能够被表示为 $k$ 个 不同的 Powerful 数之和。

【输入格式】

输入由若干行组成，第一行有一个正整数 $t(1 \le t \le 100)$，接下来 $t$ 行，每一行包括一个正整数 $n(1 \le n \le 10^{12})$。

【输出格式】

输出 $t$ 组，如果 $n$ 不能被表示为 不同的 Powerful 数之和，输出一行 $-1$，否则，输出一行答案 $k$

【样例输入】

4
7
11
240
17179869184

【样例输出】

2
3
4
1

【样例说明】

在第一组数据中，$7$ 能够被表示为 $7 = 1 + 6$，因为 $1$，$6$ 是Powerful数，所以最小的整数 $k$ 为 $2$

在第三组数据中，$240$ 能够被表示为 $240 = 24 + 32 + 64 + 120$，注意到 240 能够被表示为 $240 = 120 + 120$，但并不是一个合法的表示，因为表示 $240$ 的Powerful数必须是不同的。