#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool read(T &x) {
  int c = getchar();
  int sgn = 1;
  while (~c && c<'0' | c> '9') {
    if (c == '-') sgn = -1;
    c = getchar();
  }
  for (x = 0; ~c && '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  x *= sgn;
  return ~c;
}
struct debugger {
  template <typename T>
  debugger &operator,(const T &v) {
    cerr << v << "    ";
    return *this;
  }
} dbg;
template <class T>
void __stl_print__(T &x) {
  cerr << "[";
  for (__typeof((x).end()) i = (x).begin(); i != (x).end(); ++i)
    cerr << (i != x.begin() ? ", " : "") << *i;
  cerr << "]" << endl;
}
template <class T, class U>
inline T max(T &a, U &b) {
  return a > b ? a : b;
}
template <class T, class U>
inline T min(T &a, U &b) {
  return a < b ? a : b;
}
template <class T, class U>
inline T swap(T &a, U &b) {
  T tmp = a;
  a = b;
  b = tmp;
}
const long long INF = (1ll) << 50;
const int mx = 1e5 + 7;
const int mod = 1000000007;
const double pi = 2 * acos(0.0);
int EQ(double d) {
  if (fabs(d) < 1e-7) return 0;
  return d > 1e-7 ? 1 : -1;
}
string st;
int mem[10][4];
int get(int num) {
  if (num == 2) return 0;
  if (num == 3) return 1;
  if (num == 5) return 2;
  if (num == 7) return 3;
}
int dp[106][61][16][16];
int path[106][61][16][16];
int call(int a, int b, int c, int d) {
  if (a + b + c + d == 0) return 0;
  int &ret = dp[a][b][c][d];
  if (ret != -1) return ret;
  ret = -1e6;
  for (__typeof(9) i = (2); i <= (9); ++i) {
    if (a - mem[i][0] >= 0 && b - mem[i][1] >= 0 && c - mem[i][2] >= 0 &&
        d - mem[i][3] >= 0) {
      int tmp =
          call(a - mem[i][0], b - mem[i][1], c - mem[i][2], d - mem[i][3]) + 1;
      if (ret <= tmp) {
        ret = tmp;
        path[a][b][c][d] = i;
      }
    }
  }
  return ret;
}
void print_path(int a, int b, int c, int d) {
  if (a + b + c + d == 0) return;
  printf("%d", path[a][b][c][d]);
  int i = path[a][b][c][d];
  print_path(a - mem[i][0], b - mem[i][1], c - mem[i][2], d - mem[i][3]);
}
int main() {
  int n = ({
    int a;
    read(a);
    a;
  });
  cin >> st;
  for (__typeof(9) i = (2); i <= (9); ++i) {
    for (__typeof((4) - 1) j = (0); j <= ((4) - 1); ++j)
      mem[i][j] = mem[i - 1][j];
    int num = i, div = 2;
    while (num > 1) {
      if (num % div == 0) {
        mem[i][get(div)]++;
        num /= div;
      } else
        div++;
    }
  }
  int a = 0, b = 0, c = 0, d = 0;
  memset(dp, -1, sizeof(dp));
  for (__typeof((n)-1) i = (0); i <= ((n)-1); ++i) {
    int num = st[i] - '0';
    a += mem[num][0];
    b += mem[num][1];
    c += mem[num][2];
    d += mem[num][3];
  }
  int tmp = call(a, b, c, d);
  if (tmp > 0) {
    print_path(a, b, c, d);
    puts("");
  } else
    cout << -1 << endl;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Drazil is playing a math game with Varda.

Let's define <image> for positive integer x as a product of factorials of its digits. For example, <image>.

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:

1. x doesn't contain neither digit 0 nor digit 1.

2. <image> = <image>.

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

Note

In the first case, <image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool read(T &x) {
  int c = getchar();
  int sgn = 1;
  while (~c && c<'0' | c> '9') {
    if (c == '-') sgn = -1;
    c = getchar();
  }
  for (x = 0; ~c && '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  x *= sgn;
  return ~c;
}
struct debugger {
  template <typename T>
  debugger &operator,(const T &v) {
    cerr << v << "    ";
    return *this;
  }
} dbg;
template <class T>
void __stl_print__(T &x) {
  cerr << "[";
  for (__typeof((x).end()) i = (x).begin(); i != (x).end(); ++i)
    cerr << (i != x.begin() ? ", " : "") << *i;
  cerr << "]" << endl;
}
template <class T, class U>
inline T max(T &a, U &b) {
  return a > b ? a : b;
}
template <class T, class U>
inline T min(T &a, U &b) {
  return a < b ? a : b;
}
template <class T, class U>
inline T swap(T &a, U &b) {
  T tmp = a;
  a = b;
  b = tmp;
}
const long long INF = (1ll) << 50;
const int mx = 1e5 + 7;
const int mod = 1000000007;
const double pi = 2 * acos(0.0);
int EQ(double d) {
  if (fabs(d) < 1e-7) return 0;
  return d > 1e-7 ? 1 : -1;
}
string st;
int mem[10][4];
int get(int num) {
  if (num == 2) return 0;
  if (num == 3) return 1;
  if (num == 5) return 2;
  if (num == 7) return 3;
}
int dp[106][61][16][16];
int path[106][61][16][16];
int call(int a, int b, int c, int d) {
  if (a + b + c + d == 0) return 0;
  int &ret = dp[a][b][c][d];
  if (ret != -1) return ret;
  ret = -1e6;
  for (__typeof(9) i = (2); i <= (9); ++i) {
    if (a - mem[i][0] >= 0 && b - mem[i][1] >= 0 && c - mem[i][2] >= 0 &&
        d - mem[i][3] >= 0) {
      int tmp =
          call(a - mem[i][0], b - mem[i][1], c - mem[i][2], d - mem[i][3]) + 1;
      if (ret <= tmp) {
        ret = tmp;
        path[a][b][c][d] = i;
      }
    }
  }
  return ret;
}
void print_path(int a, int b, int c, int d) {
  if (a + b + c + d == 0) return;
  printf("%d", path[a][b][c][d]);
  int i = path[a][b][c][d];
  print_path(a - mem[i][0], b - mem[i][1], c - mem[i][2], d - mem[i][3]);
}
int main() {
  int n = ({
    int a;
    read(a);
    a;
  });
  cin >> st;
  for (__typeof(9) i = (2); i <= (9); ++i) {
    for (__typeof((4) - 1) j = (0); j <= ((4) - 1); ++j)
      mem[i][j] = mem[i - 1][j];
    int num = i, div = 2;
    while (num > 1) {
      if (num % div == 0) {
        mem[i][get(div)]++;
        num /= div;
      } else
        div++;
    }
  }
  int a = 0, b = 0, c = 0, d = 0;
  memset(dp, -1, sizeof(dp));
  for (__typeof((n)-1) i = (0); i <= ((n)-1); ++i) {
    int num = st[i] - '0';
    a += mem[num][0];
    b += mem[num][1];
    c += mem[num][2];
    d += mem[num][3];
  }
  int tmp = call(a, b, c, d);
  if (tmp > 0) {
    print_path(a, b, c, d);
    puts("");
  } else
    cout << -1 << endl;
}

```