#include <bits/stdc++.h>
using namespace std;
template <typename T>
T read() {
  T res;
  std::cin >> res;
  return res;
}
template <typename T>
void print(const T& t) {
  std::cout << t;
}
template <>
int read<int>() {
  int res;
  int cnt = scanf("%d", &res);
  return res;
}
template <>
void print<int>(const int& t) {
  printf("%d", t);
};
template <>
unsigned int read<unsigned int>() {
  unsigned int res;
  int cnt = scanf("%u", &res);
  return res;
}
template <>
void print<unsigned int>(const unsigned int& t) {
  printf("%u", t);
};
template <>
int64_t read<int64_t>() {
  int64_t res;
  int cnt = scanf("%lld", &res);
  return res;
}
template <>
void print<int64_t>(const int64_t& t) {
  printf("%lld", t);
};
template <>
float read<float>() {
  float res;
  int cnt = scanf("%f", &res);
  return res;
}
template <>
void print<float>(const float& t) {
  printf("%f", t);
};
template <>
double read<double>() {
  double res;
  int cnt = scanf("%lf", &res);
  return res;
}
template <>
void print<double>(const double& t) {
  printf("%lf", t);
};
template <>
char read<char>() {
  char res;
  int cnt = scanf("%c", &res);
  return res;
}
template <>
void print<char>(const char& t) {
  printf("%c", t);
};
namespace internal {
template <typename ValueT>
class IterableRange {
 public:
  class iterator {
   public:
    iterator(ValueT v__) : v_(v__) {}
    iterator& operator++() {
      ++v_;
      return *this;
    }
    bool operator==(iterator rhs) const { return v_ == rhs.v_; }
    bool operator!=(iterator rhs) const { return v_ != rhs.v_; }
    ValueT operator*() const { return v_; }
    ValueT operator->() const { return v_; }

   private:
    ValueT v_ = {};
  };
  IterableRange(ValueT begin__, ValueT end__)
      : begin_value_(std::min(begin__, end__)), end_value_(end__) {}
  iterator begin() const { return {begin_value_}; }
  iterator end() const { return {end_value_}; }

 private:
  ValueT begin_value_ = {};
  ValueT end_value_ = {};
};
}  // namespace internal
template <typename ValueT>
internal::IterableRange<ValueT> range(ValueT end) {
  return {{}, end};
}
template <typename ValueT>
internal::IterableRange<ValueT> range(ValueT begin, ValueT end) {
  return {begin, end};
}
template <typename T>
std::vector<T> readVector(size_t size) {
  std::vector<T> res(size);
  for (auto& elt : res) elt = read<T>();
  return res;
}
inline bool isPrime(uint64_t n) {
  if (n == 1) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;
  for (uint64_t div = 3; div * div <= n; div += 2)
    if (n % div == 0) return false;
  return true;
}
inline std::vector<uint64_t> generatePrimesUntil(uint64_t upperBound) {
  if (upperBound < 2) return {};
  std::vector<uint64_t> result = {2};
  for (uint64_t candidate = 3; candidate <= upperBound; candidate += 2) {
    bool divisibleByPrevious = false;
    for (size_t divisorIndex = 1;
         divisorIndex < result.size() &&
         result[divisorIndex] * result[divisorIndex] <= candidate;
         ++divisorIndex) {
      if (candidate % result[divisorIndex] == 0) {
        divisibleByPrevious = true;
        break;
      }
    }
    if (!divisibleByPrevious) result.push_back(candidate);
  }
  return result;
}
inline std::vector<std::pair<uint64_t, uint64_t>> decomposeToPrimePowers(
    uint64_t n) {
  std::vector<std::pair<uint64_t, uint64_t>> result;
  auto tryPrime = [&](uint64_t p) {
    if (n % p == 0) {
      result.push_back({p, 0});
      while (n % p == 0) {
        n /= p;
        result.back().second++;
      }
    }
  };
  tryPrime(2);
  for (uint64_t primeCandidate = 3; primeCandidate * primeCandidate <= n;
       primeCandidate += 2)
    tryPrime(primeCandidate);
  if (n > 1) result.push_back({n, 1});
  return result;
}
using namespace std;
class Solver665D {
 public:
  void run();
};
void Solver665D::run() {
  int n = read<int>();
  auto a = readVector<int>(n);
  int onesCnt = count(begin(a), end(a), 1);
  int indPrePrime = -1;
  for (int i : range(n)) {
    auto elt = a[i];
    if (elt > 1 && isPrime(elt + 1)) indPrePrime = i;
  }
  auto primes = generatePrimesUntil(2e6);
  unordered_set<int> primeSet(begin(primes), end(primes));
  for (int i : range(n)) {
    auto elt = a[i];
    if (elt > 1 && primeSet.count(elt + 1)) indPrePrime = i;
  }
  pair<int, int> indPrimePair = {-1, -1};
  for (int i : range(n)) {
    for (int j : range(i)) {
      int cand = a[i] + a[j];
      if (cand > 2 && primeSet.count(cand)) {
        indPrimePair = {i, j};
        break;
      }
    }
    if (indPrimePair.first > 0) break;
  }
  int cntWithOnes = onesCnt + ((indPrePrime != -1) ? 1 : 0);
  int cntWithoutOnes = (indPrimePair.first != -1) ? 2 : 1;
  cout << max(cntWithOnes, cntWithoutOnes) << "\n";
  if (cntWithOnes >= cntWithoutOnes) {
    for (int i : range(onesCnt)) cout << "1 ";
    if (indPrePrime != -1) cout << a[indPrePrime];
  } else {
    if (indPrimePair.first != -1)
      cout << a[indPrimePair.first] << " " << a[indPrimePair.second];
    else
      cout << a[0];
  }
}
int main() {
  Solver665D solver;
  solver.run();
}

### Prompt

Create a solution in cpp for the following problem:

A tuple of positive integers {x1, x2, ..., xk} is called simple if for all pairs of positive integers (i, j) (1 ≤ i < j ≤ k), xi + xj is a prime.

You are given an array a with n positive integers a1, a2, ..., an (not necessary distinct). You want to find a simple subset of the array a with the maximum size.

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Let's define a subset of the array a as a tuple that can be obtained from a by removing some (possibly all) elements of it.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of integers in the array a.

The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.

Output

On the first line print integer m — the maximum possible size of simple subset of a.

On the second line print m integers bl — the elements of the simple subset of the array a with the maximum size.

If there is more than one solution you can print any of them. You can print the elements of the subset in any order.

Examples

Input

2
2 3


Output

2
3 2


Input

2
2 2


Output

1
2


Input

3
2 1 1


Output

3
1 1 2


Input

2
83 14


Output

2
14 83

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T read() {
  T res;
  std::cin >> res;
  return res;
}
template <typename T>
void print(const T& t) {
  std::cout << t;
}
template <>
int read<int>() {
  int res;
  int cnt = scanf("%d", &res);
  return res;
}
template <>
void print<int>(const int& t) {
  printf("%d", t);
};
template <>
unsigned int read<unsigned int>() {
  unsigned int res;
  int cnt = scanf("%u", &res);
  return res;
}
template <>
void print<unsigned int>(const unsigned int& t) {
  printf("%u", t);
};
template <>
int64_t read<int64_t>() {
  int64_t res;
  int cnt = scanf("%lld", &res);
  return res;
}
template <>
void print<int64_t>(const int64_t& t) {
  printf("%lld", t);
};
template <>
float read<float>() {
  float res;
  int cnt = scanf("%f", &res);
  return res;
}
template <>
void print<float>(const float& t) {
  printf("%f", t);
};
template <>
double read<double>() {
  double res;
  int cnt = scanf("%lf", &res);
  return res;
}
template <>
void print<double>(const double& t) {
  printf("%lf", t);
};
template <>
char read<char>() {
  char res;
  int cnt = scanf("%c", &res);
  return res;
}
template <>
void print<char>(const char& t) {
  printf("%c", t);
};
namespace internal {
template <typename ValueT>
class IterableRange {
 public:
  class iterator {
   public:
    iterator(ValueT v__) : v_(v__) {}
    iterator& operator++() {
      ++v_;
      return *this;
    }
    bool operator==(iterator rhs) const { return v_ == rhs.v_; }
    bool operator!=(iterator rhs) const { return v_ != rhs.v_; }
    ValueT operator*() const { return v_; }
    ValueT operator->() const { return v_; }

   private:
    ValueT v_ = {};
  };
  IterableRange(ValueT begin__, ValueT end__)
      : begin_value_(std::min(begin__, end__)), end_value_(end__) {}
  iterator begin() const { return {begin_value_}; }
  iterator end() const { return {end_value_}; }

 private:
  ValueT begin_value_ = {};
  ValueT end_value_ = {};
};
}  // namespace internal
template <typename ValueT>
internal::IterableRange<ValueT> range(ValueT end) {
  return {{}, end};
}
template <typename ValueT>
internal::IterableRange<ValueT> range(ValueT begin, ValueT end) {
  return {begin, end};
}
template <typename T>
std::vector<T> readVector(size_t size) {
  std::vector<T> res(size);
  for (auto& elt : res) elt = read<T>();
  return res;
}
inline bool isPrime(uint64_t n) {
  if (n == 1) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;
  for (uint64_t div = 3; div * div <= n; div += 2)
    if (n % div == 0) return false;
  return true;
}
inline std::vector<uint64_t> generatePrimesUntil(uint64_t upperBound) {
  if (upperBound < 2) return {};
  std::vector<uint64_t> result = {2};
  for (uint64_t candidate = 3; candidate <= upperBound; candidate += 2) {
    bool divisibleByPrevious = false;
    for (size_t divisorIndex = 1;
         divisorIndex < result.size() &&
         result[divisorIndex] * result[divisorIndex] <= candidate;
         ++divisorIndex) {
      if (candidate % result[divisorIndex] == 0) {
        divisibleByPrevious = true;
        break;
      }
    }
    if (!divisibleByPrevious) result.push_back(candidate);
  }
  return result;
}
inline std::vector<std::pair<uint64_t, uint64_t>> decomposeToPrimePowers(
    uint64_t n) {
  std::vector<std::pair<uint64_t, uint64_t>> result;
  auto tryPrime = [&](uint64_t p) {
    if (n % p == 0) {
      result.push_back({p, 0});
      while (n % p == 0) {
        n /= p;
        result.back().second++;
      }
    }
  };
  tryPrime(2);
  for (uint64_t primeCandidate = 3; primeCandidate * primeCandidate <= n;
       primeCandidate += 2)
    tryPrime(primeCandidate);
  if (n > 1) result.push_back({n, 1});
  return result;
}
using namespace std;
class Solver665D {
 public:
  void run();
};
void Solver665D::run() {
  int n = read<int>();
  auto a = readVector<int>(n);
  int onesCnt = count(begin(a), end(a), 1);
  int indPrePrime = -1;
  for (int i : range(n)) {
    auto elt = a[i];
    if (elt > 1 && isPrime(elt + 1)) indPrePrime = i;
  }
  auto primes = generatePrimesUntil(2e6);
  unordered_set<int> primeSet(begin(primes), end(primes));
  for (int i : range(n)) {
    auto elt = a[i];
    if (elt > 1 && primeSet.count(elt + 1)) indPrePrime = i;
  }
  pair<int, int> indPrimePair = {-1, -1};
  for (int i : range(n)) {
    for (int j : range(i)) {
      int cand = a[i] + a[j];
      if (cand > 2 && primeSet.count(cand)) {
        indPrimePair = {i, j};
        break;
      }
    }
    if (indPrimePair.first > 0) break;
  }
  int cntWithOnes = onesCnt + ((indPrePrime != -1) ? 1 : 0);
  int cntWithoutOnes = (indPrimePair.first != -1) ? 2 : 1;
  cout << max(cntWithOnes, cntWithoutOnes) << "\n";
  if (cntWithOnes >= cntWithoutOnes) {
    for (int i : range(onesCnt)) cout << "1 ";
    if (indPrePrime != -1) cout << a[indPrePrime];
  } else {
    if (indPrimePair.first != -1)
      cout << a[indPrimePair.first] << " " << a[indPrimePair.second];
    else
      cout << a[0];
  }
}
int main() {
  Solver665D solver;
  solver.run();
}

```