#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<cstring>
#include<string>
#include <math.h>
#include<algorithm>
#include<functional>
#define int long long
#define ll long long
#define inf  1000000007
#define mod 1000000007
#define PI acos(-1)
#define pa pair<int,int>
#define pal pair<ll,ll>
#define ppa pair<int,pa>
#define EPS (1e-6)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

class Point{
  public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y) {}
  Point operator + (Point p) {return Point(x+p.x,y+p.y);}
  Point operator - (Point p) {return Point(x-p.x,y-p.y);}
  Point operator * (double a) {return Point(x*a,y*a);}
  Point operator / (double a) {return Point(x/a,y/a);}
  double absv() {return sqrt(norm());}
  double norm() {return x*x+y*y;}
  bool operator < (const Point &p) const{
    return x != p.x ? x<p.x: y<p.y;
  }
  bool operator == (const Point &p) const{
    return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
  }
};
typedef Point Vector;

struct Segment{
Point p1,p2;
};

double hen(Vector a){
if(fabs(a.x)<EPS && a.y>0) return acos(0);
else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
else if(fabs(a.y)<EPS && a.x>0) return 0.0;
else if(a.y>0) return acos(a.x/a.absv());
else return 2*acos(0)+acos(-a.x/a.absv());

}
double cross(Vector a,Vector b){
  return a.x*b.y-a.y*b.x;
}

Point inter(Point a1, Point a2, Point b1, Point b2) {
  Point a = a2 - a1;
   Point  b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}

double dot(Vector a,Vector b){
  return a.x*b.x+a.y*b.y;
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int ru[11]={1,2,4,8,16,32,64,128,256,512,1024};

ll frac[100010];
ll inv[100010];

ll saikif(ll a,int n){
  if(n==1) return a%mod;
  else if(n%2==0){
    ll q=saikif(a,n/2);
    return (q*q)%mod;
  }
  else return (a*saikif(a,n-1))%mod;
}

int beki[20];


void gyakugen(){
  frac[0]=1;
  for(int i=1;i<=100000;i++) frac[i]=(frac[i-1]*i)%mod;
  for(int i=0;i<=100000;i++) inv[i]=saikif(frac[i],mod-2);
}

//------------kokomade--tenpure---------
int l[20];
map<int,int> ma;




vector<ll> ve;
int saiki(ll n){
	int q=0;
	vector<int> ans;
	while(1){
		if(beki[q]<n) q++;
		else break;
	}
//	cout<<n<<" "<<q<<endl;
	
	if (n==-1) return -1;
	if(n==1) return 0;
	if(ma.find(n) != ma.end()) return ma[n];
	for(int i=0;i<l[q];i++){
		if(n%ve[i]==0){
			int u=saiki(n/ve[i]);
			
			if(u>=0) ans.push_back( saiki(n/ve[i])+1);
	//		cout<<saiki(n/ve[i])+1<<endl;
		}
	}
	int d=0;
	if(ans.size()==0){
		ma[n]=-1;
	//	cout<<n<<" "<<ma[n]<<endl;
		return -1;
	}
	else{
		for(int i=0;i<ans.size();i++){
			d=max(d,ans[i]);
		}
		ma[n]=d;
	//	cout<<n<<" "<<ma[n]<<endl;
		return d;
	}

}






signed main(){
	beki[0]=1;
for(int i=1;i<=18;i++){
	beki[i] = beki[i-1]*10;
}

int r;
	ma[-1]=-1;
	ma[1]=1;
	for(int i=1;i<=18;i++){
		int ma= (1<<i);
		for(int j=0;j<ma;j++){
			r=0;
			for(int k=0;k<i;k++){
				if((j>>k)&1 ==1  ) r=r*10+2;
				else r=r*10+8;
			}
			ve.push_back(r);
			
		}
		l[i]=ve.size();
	//	cout<<i<<" "<<l[i]<<endl;
	}

	 
	ll n;
	cin>>n;
	if(n==1){
		cout<<"-1"<<endl;
		return 0;
	}
	int q=0;
		while(1){
		if(beki[q]<n) q++;
		else break;
	}
	//cout<<q<<endl;
	
	cout<<saiki(n)<<endl;
	
	
	return 0;
}
### Prompt

Generate 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 <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<cstring>
#include<string>
#include <math.h>
#include<algorithm>
#include<functional>
#define int long long
#define ll long long
#define inf  1000000007
#define mod 1000000007
#define PI acos(-1)
#define pa pair<int,int>
#define pal pair<ll,ll>
#define ppa pair<int,pa>
#define EPS (1e-6)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

class Point{
  public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y) {}
  Point operator + (Point p) {return Point(x+p.x,y+p.y);}
  Point operator - (Point p) {return Point(x-p.x,y-p.y);}
  Point operator * (double a) {return Point(x*a,y*a);}
  Point operator / (double a) {return Point(x/a,y/a);}
  double absv() {return sqrt(norm());}
  double norm() {return x*x+y*y;}
  bool operator < (const Point &p) const{
    return x != p.x ? x<p.x: y<p.y;
  }
  bool operator == (const Point &p) const{
    return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
  }
};
typedef Point Vector;

struct Segment{
Point p1,p2;
};

double hen(Vector a){
if(fabs(a.x)<EPS && a.y>0) return acos(0);
else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
else if(fabs(a.y)<EPS && a.x>0) return 0.0;
else if(a.y>0) return acos(a.x/a.absv());
else return 2*acos(0)+acos(-a.x/a.absv());

}
double cross(Vector a,Vector b){
  return a.x*b.y-a.y*b.x;
}

Point inter(Point a1, Point a2, Point b1, Point b2) {
  Point a = a2 - a1;
   Point  b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}

double dot(Vector a,Vector b){
  return a.x*b.x+a.y*b.y;
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int ru[11]={1,2,4,8,16,32,64,128,256,512,1024};

ll frac[100010];
ll inv[100010];

ll saikif(ll a,int n){
  if(n==1) return a%mod;
  else if(n%2==0){
    ll q=saikif(a,n/2);
    return (q*q)%mod;
  }
  else return (a*saikif(a,n-1))%mod;
}

int beki[20];


void gyakugen(){
  frac[0]=1;
  for(int i=1;i<=100000;i++) frac[i]=(frac[i-1]*i)%mod;
  for(int i=0;i<=100000;i++) inv[i]=saikif(frac[i],mod-2);
}

//------------kokomade--tenpure---------
int l[20];
map<int,int> ma;




vector<ll> ve;
int saiki(ll n){
	int q=0;
	vector<int> ans;
	while(1){
		if(beki[q]<n) q++;
		else break;
	}
//	cout<<n<<" "<<q<<endl;
	
	if (n==-1) return -1;
	if(n==1) return 0;
	if(ma.find(n) != ma.end()) return ma[n];
	for(int i=0;i<l[q];i++){
		if(n%ve[i]==0){
			int u=saiki(n/ve[i]);
			
			if(u>=0) ans.push_back( saiki(n/ve[i])+1);
	//		cout<<saiki(n/ve[i])+1<<endl;
		}
	}
	int d=0;
	if(ans.size()==0){
		ma[n]=-1;
	//	cout<<n<<" "<<ma[n]<<endl;
		return -1;
	}
	else{
		for(int i=0;i<ans.size();i++){
			d=max(d,ans[i]);
		}
		ma[n]=d;
	//	cout<<n<<" "<<ma[n]<<endl;
		return d;
	}

}






signed main(){
	beki[0]=1;
for(int i=1;i<=18;i++){
	beki[i] = beki[i-1]*10;
}

int r;
	ma[-1]=-1;
	ma[1]=1;
	for(int i=1;i<=18;i++){
		int ma= (1<<i);
		for(int j=0;j<ma;j++){
			r=0;
			for(int k=0;k<i;k++){
				if((j>>k)&1 ==1  ) r=r*10+2;
				else r=r*10+8;
			}
			ve.push_back(r);
			
		}
		l[i]=ve.size();
	//	cout<<i<<" "<<l[i]<<endl;
	}

	 
	ll n;
	cin>>n;
	if(n==1){
		cout<<"-1"<<endl;
		return 0;
	}
	int q=0;
		while(1){
		if(beki[q]<n) q++;
		else break;
	}
	//cout<<q<<endl;
	
	cout<<saiki(n)<<endl;
	
	
	return 0;
}
```