#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

ll n;
vector<ll> num;
unordered_map<ll, int> dp;

inline int rec(ll x){
	if(dp.count(x)) return dp[x];
	int &res = dp[x];
	if(x == 1) return res = 0;
	
	res = -inf;
	for(ll m : num){
		if(x % m == 0) res = max(res, 1 + rec(x / m));
		if(m >= x) break;
	}
	if(res < 0) res = -inf;
	return res;
}

int main(){
	for(int keta = 1; keta <= 18; keta++){
		rep(i, 1 << keta){
			ll m = 0;
			rep(j, keta){
				if(m * 10.0 > 1.1e18) {m = -1; break; }
				m *= 10;
				m += i >> j & 1 ? 8 : 2;
			}
			if(m > 0) num.pb(m);
		}
	}
	sort(all(num));
	
	cin >> n;
	int res = n > 1 ? rec(n) : -inf;
	cout << (res < 0 ? -1 : res) << endl;
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

ll n;
vector<ll> num;
unordered_map<ll, int> dp;

inline int rec(ll x){
	if(dp.count(x)) return dp[x];
	int &res = dp[x];
	if(x == 1) return res = 0;
	
	res = -inf;
	for(ll m : num){
		if(x % m == 0) res = max(res, 1 + rec(x / m));
		if(m >= x) break;
	}
	if(res < 0) res = -inf;
	return res;
}

int main(){
	for(int keta = 1; keta <= 18; keta++){
		rep(i, 1 << keta){
			ll m = 0;
			rep(j, keta){
				if(m * 10.0 > 1.1e18) {m = -1; break; }
				m *= 10;
				m += i >> j & 1 ? 8 : 2;
			}
			if(m > 0) num.pb(m);
		}
	}
	sort(all(num));
	
	cin >> n;
	int res = n > 1 ? rec(n) : -inf;
	cout << (res < 0 ? -1 : res) << endl;
	return 0;
}
```