#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

bool is_good(string n, set<char> s = {'2', '8'}) {
    EACH(d, n) {
        if (s.count(d) == 0) {
            return false;
        }
    }
    return true;
}
ll power(ll x, ll n) {
    ll res = 1;
    REP(i, n) res *= x;
    return res;
}
vector<ll> gns;
ll solve(ll n, ll idx) {
    if (idx == gns.size()) return -1;
    ll res = -1;
    if (is_good(to_string(n))) res = max(res, 1LL);
    if (n % gns[idx] == 0) {
        ll r = solve(n/gns[idx], idx);
        if (r >= 0) {
            res = max(res, r+1);
        }
    }
    res = max(res, solve(n, idx+1));
    return res;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    string nstr; cin >> nstr;
    ll n = stoll(nstr);
    vector<ll> gn = {2, 8};
    FOR(w, 1, 17) {
        REP(i, (1<<w)) {
            ll val = 0;
            REP(j, w) {
                val = val * 10 + gn[(i>>(w-j-1))&1];
            }
            if (val == 222888288 || is_good(to_string(val), {'8'})) continue;
            if (n % val == 0) gns.pb(val);
        }
    }
    cout << solve(n, 0) << endl;
}
### Prompt

Create a solution in cpp for 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 <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

bool is_good(string n, set<char> s = {'2', '8'}) {
    EACH(d, n) {
        if (s.count(d) == 0) {
            return false;
        }
    }
    return true;
}
ll power(ll x, ll n) {
    ll res = 1;
    REP(i, n) res *= x;
    return res;
}
vector<ll> gns;
ll solve(ll n, ll idx) {
    if (idx == gns.size()) return -1;
    ll res = -1;
    if (is_good(to_string(n))) res = max(res, 1LL);
    if (n % gns[idx] == 0) {
        ll r = solve(n/gns[idx], idx);
        if (r >= 0) {
            res = max(res, r+1);
        }
    }
    res = max(res, solve(n, idx+1));
    return res;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    string nstr; cin >> nstr;
    ll n = stoll(nstr);
    vector<ll> gn = {2, 8};
    FOR(w, 1, 17) {
        REP(i, (1<<w)) {
            ll val = 0;
            REP(j, w) {
                val = val * 10 + gn[(i>>(w-j-1))&1];
            }
            if (val == 222888288 || is_good(to_string(val), {'8'})) continue;
            if (n % val == 0) gns.pb(val);
        }
    }
    cout << solve(n, 0) << endl;
}
```