Problem - 1646C. Factorials and Powers of Two - Codeforces

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=2d or m=d!, where d!=1⋅2⋅…⋅d (in particular, 0!=1). For example 1, 4, and 6 are powerful numbers, because 1=1!, 4=22, 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.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.

A test case consists of only one line, containing one integer n (1≤n≤1012).

Output

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.

Example

input

4
7
11
240
17179869184

output

2
3
4
1

Problem analysis

The question is , Give you a number , Let me show you how many this number can be at least 2 The power of （1,2,4,8 etc. ） And factorial （1,2,6,24） Other components .

First , Every number must be combined , Because all numbers can be expressed in binary , There is x individual 1, It shows that this number can be used x individual 2 To the power of , So we are looking for the combination of factorials , Can you find something smaller x.

The array range of topics is 10^12 , Then the factorial maximum is 15！, You count 0！, Is the total 16 Number . We can use binary enumeration method to enumerate （ from 1 Enumerate to 2^{16, See which position on the binary bit has 1, Let's take whichever number , So you can get this 16 Number all combinations ）. Calculate the sum , Calculation ：（ Order multiplier used +n After subtracting and combining, it is obtained in binary 1 Number ）, And maintain the minimum value . The time complexity is O(n*2}16 )

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5050;

int lowbit(ll x)
{
    int cnt = 0;
    while (x)
    {
        if (x % 2 == 1)cnt++;
        x /= 2;
    }
    return cnt;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    vector<ll>ans(16);
    ans[0] = 1;
    for (int i = 1; i <= 15; i++)ans[i] = ans[i - 1] * i;
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        ll res = lowbit(n), sum = 0, cnt = 0;
        for (ll i = 1; i <= (1 << 16); i++)
        {
            sum = 0, cnt = 0;
            for (ll j = 0; j <= 15; j++)
            {
                if (((i >> j) & 1))
                {
                    sum += ans[j];
                    cnt++;
                }
            }
            if (sum <= n)
            {
                res = min(cnt + lowbit(n - sum), res);
            }
        }
        cout << res << endl;
    }
    return 0;
}