Factorials and Powers of Two

题意翻译

我们称一个数 $m$ 是好数，当且仅当 $m$ 为形如 $d!$ 或者 $2^d$ 的数。现在给定一个整数 $n$，请求出最小的整数 $k$，使得 $n$ 可以表示成 $k$ 个**互不相同**的好数的和。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 100$。 - $1\leqslant n\leqslant 10^{12}$。 Translated by Eason_AC

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

4
7
11
240
17179869184

输出样例 #1

2
3
4
1

说明

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