#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("0"); return 0;}
using namespace std;
typedef long long int ll;
typedef pair<ll,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{for(T&x:v)i>>x;return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;for(T&x:v)s<<' '<<x;return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}

const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

vl d;
void dfs(ll n, ll x) {
  if (x > n) return;
  if (x && n%x == 0) d.pb(x);
  x = x*10+2;
  dfs(n,x);
  x += 6;
  dfs(n,x);
}
map<P,int> mp;
int sol(ll x, int i) {
  if (x == 1) return 0;
  P p(x,i);
  if (mp.count(p)) return mp[p];
  int res = -INF;
  for (; i < sz(d) && x >= d[i]; ++i) {
    if (x%d[i] == 0) maxs(res, sol(x/d[i],i)+1);
  }
  return mp[p] = res;
}

int main() {
  ll n;
  cin >> n;
  if (n == 1) {
    cout<<-1<<endl;
    return 0;
  }
  dfs(n,0);
  sort(rng(d));
  int ans = sol(n,0);
  if (ans < 0) ans = -1;
  cout<<ans<<endl;
  return 0;
}
### Prompt

Please create a solution in Cpp 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 <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("0"); return 0;}
using namespace std;
typedef long long int ll;
typedef pair<ll,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{for(T&x:v)i>>x;return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;for(T&x:v)s<<' '<<x;return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}

const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

vl d;
void dfs(ll n, ll x) {
  if (x > n) return;
  if (x && n%x == 0) d.pb(x);
  x = x*10+2;
  dfs(n,x);
  x += 6;
  dfs(n,x);
}
map<P,int> mp;
int sol(ll x, int i) {
  if (x == 1) return 0;
  P p(x,i);
  if (mp.count(p)) return mp[p];
  int res = -INF;
  for (; i < sz(d) && x >= d[i]; ++i) {
    if (x%d[i] == 0) maxs(res, sol(x/d[i],i)+1);
  }
  return mp[p] = res;
}

int main() {
  ll n;
  cin >> n;
  if (n == 1) {
    cout<<-1<<endl;
    return 0;
  }
  dfs(n,0);
  sort(rng(d));
  int ans = sol(n,0);
  if (ans < 0) ans = -1;
  cout<<ans<<endl;
  return 0;
}
```