阶乘与二的幂

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

如果一个数是 $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$。

样例输入 1

4
7
11
240
17179869184

样例输出 1

2
3
4
1

数据范围

对于所有数据，$1\le t\le100$，$1\le n\le10^{12}$。相同数值的强大数只能使用一次。