如果一个数字是 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$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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
注意
在第一个测试用例中,$$$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$$$。