Drazil is playing a math game with Varda.
Let’s define for positive integer x as a product of factorials of its digits. For example, .
First, they choose a decimal number a consisting of n digits that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying following two conditions:
-
x doesn’t contain neither digit 0 nor digit 1.
-
F(x) = F(a)
Help friends find such number.
Input
The first line contains an integer n (1 ≤ n ≤ 15) — the number of digits in a.
The second line contains n digits of a. There is at least one digit in a that is larger than 1. Number a may possibly contain leading zeroes.
Output
Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.
Examples
Input
4
1234
Output
33222
Input
3
555
Output
555
思路：
对于每一个数字，如6
我们把它分成几个阶乘相乘的形式
让能分的阶乘数尽量地多，最后构成的数必然最大
你可用10分钟手算
1!=1!1!=1!
2!=2!2!=2!
3!=3!3!=3!
4!=3!*2!*2!4!=3!∗2!∗2!
5!=5!5!=5!
6!=5!*3!6!=5!∗3!
7!=7!7!=7!
8!=7!*2!*2!*2!8!=7!∗2!∗2!∗2!
9!=7!*3!*3!*2!9!=7!∗3!∗3!∗2!
把这些数放入一个数组，再从大到小排序，输出答案
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.next();
int[] a = new int[20];
for(int i=0;i<n;i++){
int t = s.charAt(i)-'0';
if(t==2)a[2]++;
if(t==3){
a[3]++;
}
if(t==4){
a[2]+=2;
a[3]++;
}
if(t==5){
a[5]++;
}
if(t==6){
a[3]++;
a[5]++;
}
if(t==7){
a[7]++;
}
if(t==8){
a[2]+=3;
a[7]++;
}
if(t==9){
a[2]++;
a[3]+=2;
a[7]++;
}
}
for(int i=9;i>1;i--){
for(int j=0;j<a[i];j++){
System.out.print(i);
}
}
}
}