#include<iostream>
#include<vector>
#include<cassert>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<tuple>
#include<numeric>
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef ll int__;
#define rep(i,j) for(int__ i=0;i<(int__)(j);i++)
#define repeat(i,j,k) for(int__ i=(j);i<(int__)(k);i++)
#define all(v) v.begin(),v.end()
const int INF = 1 << 30;
template<typename T>
ostream& operator << (ostream &os , const vector<T> &v){
    rep(i,v.size()) os << v[i] << (i!=v.size()-1 ? " " : ""); return os;
}

template<typename T>
istream& operator >> (istream &is , vector<T> &v){
    rep(i,v.size()) is >> v[i]; return is;
}

pair<int,ll> div2(ll n){
    int cnt = 0;
    while(n % 2 == 0) n /= 2, cnt++;
    return make_pair(cnt, n);
}

vector<pair<int,ll>> calc_good_number(ll upper){
    vector<pair<int,ll>> res;
    set<ll> memo;
    queue<ll> que;
    que.push(2);
    que.push(8);
    while(que.size()){
        ll n = que.front(); que.pop();
        auto p = div2(n);
        if(not memo.count(p.second)){
            res.push_back(div2(n));
            memo.insert(p.second);
        }
        
        if(n < upper){
            que.push(n * 10 + 2);
            que.push(n * 10 + 8);
        }
    }
    return res;
}

map<pair<int,ll>, int> dp;
int dfs(const vector<pair<int,ll>> &good_number, int now, int left2, ll left){
    if(left == 1) return left2;
    if(dp.count(make_pair(left2, left))) return dp[make_pair(left2, left)];
    int ans = -INF;
    while(now < (int)good_number.size()){
        if(left % good_number[now].second == 0 and left2 >= good_number[now].first){
            ans = max(ans, dfs(good_number, now, left2 - good_number[now].first, left / good_number[now].second));
        }
        now++;
    }
    return dp[make_pair(left2, left)] = ans + 1;
}


bool solve(){
    ll n; cin >> n;
    if(n == 1){
        cout << -1 << endl;
        return 0;
    }
    vector<pair<int,ll>> good_number = calc_good_number(n);
    //rep(i, good_number.size()) cerr << good_number[i].second << endl;
    int left2 = 0;
    while(n % 2 == 0) n /= 2, left2++;
    int res = dfs(good_number, 0, left2, n);
    cout << (res < 0 ? -1 : res) << endl;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    while(solve());
    return 0;
}
### Prompt

Please formulate a CPP solution to the following problem:

Problem statement

Cards with ranks of $ 2 $ and $ 8 $ are powerful in card game millionaires. Therefore, we call an integer consisting of only the numbers $ 2 $ and $ 8 $ in $ 10 $ decimal notation a good integer. The best integers are listed from the smallest to $ 2, 8, 22, 28, 82, 88, \ cdots $.

Let $ n $ be a positive integer. When $ n $ can be expressed in the form of a product of good integers, find the maximum product. If you can't, output $ -1 $.

Constraint

$ 1 \ leq n \ leq 10 ^ {18} $

sample

Sample input 1


1


Sample output 1


-1


Sample input 2


2


Sample output 2


1


Sample input 3


88


Sample output 3


3


It can be expressed as $ 2 \ times 2 \ times 22 $.

Sample input 4


100


Sample output 4


-1


Sample input 5


173553147234869248


Sample output 5


11


It can be expressed as $ 2 ^ 6 \ times 28 \ times 2222 ^ 3 \ times 8828 $.



input

$ n $

output

Print the answer on the $ 1 $ line.

Example

Input

1


Output

-1

### Response

```cpp
#include<iostream>
#include<vector>
#include<cassert>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<tuple>
#include<numeric>
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef ll int__;
#define rep(i,j) for(int__ i=0;i<(int__)(j);i++)
#define repeat(i,j,k) for(int__ i=(j);i<(int__)(k);i++)
#define all(v) v.begin(),v.end()
const int INF = 1 << 30;
template<typename T>
ostream& operator << (ostream &os , const vector<T> &v){
    rep(i,v.size()) os << v[i] << (i!=v.size()-1 ? " " : ""); return os;
}

template<typename T>
istream& operator >> (istream &is , vector<T> &v){
    rep(i,v.size()) is >> v[i]; return is;
}

pair<int,ll> div2(ll n){
    int cnt = 0;
    while(n % 2 == 0) n /= 2, cnt++;
    return make_pair(cnt, n);
}

vector<pair<int,ll>> calc_good_number(ll upper){
    vector<pair<int,ll>> res;
    set<ll> memo;
    queue<ll> que;
    que.push(2);
    que.push(8);
    while(que.size()){
        ll n = que.front(); que.pop();
        auto p = div2(n);
        if(not memo.count(p.second)){
            res.push_back(div2(n));
            memo.insert(p.second);
        }
        
        if(n < upper){
            que.push(n * 10 + 2);
            que.push(n * 10 + 8);
        }
    }
    return res;
}

map<pair<int,ll>, int> dp;
int dfs(const vector<pair<int,ll>> &good_number, int now, int left2, ll left){
    if(left == 1) return left2;
    if(dp.count(make_pair(left2, left))) return dp[make_pair(left2, left)];
    int ans = -INF;
    while(now < (int)good_number.size()){
        if(left % good_number[now].second == 0 and left2 >= good_number[now].first){
            ans = max(ans, dfs(good_number, now, left2 - good_number[now].first, left / good_number[now].second));
        }
        now++;
    }
    return dp[make_pair(left2, left)] = ans + 1;
}


bool solve(){
    ll n; cin >> n;
    if(n == 1){
        cout << -1 << endl;
        return 0;
    }
    vector<pair<int,ll>> good_number = calc_good_number(n);
    //rep(i, good_number.size()) cerr << good_number[i].second << endl;
    int left2 = 0;
    while(n % 2 == 0) n /= 2, left2++;
    int res = dfs(good_number, 0, left2, n);
    cout << (res < 0 ? -1 : res) << endl;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    while(solve());
    return 0;
}
```