# FACT

ZJS likes to show off his wonderful calculator. His calculator can do FACT operation which means can divide an integer to some primes' products. For example, Fact(30) will display which is a string of length 5. Fact(60) will display which is a string of length 6.

Now he wonders among all integers i under a given number N, what's the max length of the string F(i) produces?

If there are many answers print any.

Note: Fact(1)'s length is 0

# Example

N=30
Output should be 30 because 30 is the only number that length is 5.
N=65
Output should be 60 because 60 is the only number that length is 6.

# Constriants

Subtask1(33%):2<=N<=1000
Subtask2(33%):2<=N<=1e9
Subtask3(33%):2<=N<=1e12
Subtask4(1%):2<=N<=1e18

# Hacker XGN

Anyone wanna use greedy? Test the data 9240
Answer should be 12(one possible output is 8580).
A short program for you to look for the rules:

#include <bits/stdc++.h>
using namespace std;

string toString(int num){
string ans="";
while(num!=0){
char c=(num%10+'0');
ans=c+ans;
num/=10;
}
return ans;
}
string fact(int num){
string s="";
for(int i=2;i*i<=num;i++){
if(num%i==0){
int cnt=0;
while(num%i==0){
num/=i;
cnt++;
}
if(cnt==1){
s+=toString(i)+"*";
}else{
s+=toString(i)+""+toString(cnt)+"*";
}

}
}
if(num!=1){
s+=toString(num)+"+";
}
s.pop_back();
return s;
}
int main() {
int n;
cin>>n;

int mx=0;
int mxl=0;
for(int i=2;i<=n;i++){
string s=fact(i);
if(s.length()>=mxl){
mxl=s.length();
mx=i;
}
// cout<<i<<" fact="<<fact(i)<<" length="<<fact(i).length()<<endl;
}

cout<<mx<<" fact="<<fact(mx)<<" length="<<mxl<<endl;
return 0;
}


# Solution By MonkeyKing

Greedy can be found by greedying through digits.