#include <bits/stdc++.h>
const double PI =
    3.14159265358979323846264338327950288419716939937510582097494459230;
#pragma warning(disable : 4996);
using namespace std;
const long long inf = (long long)1e18 + 111;
const int iinf = (int)1e9 + 111;
const int SIZE = 1e5 + 11;
int n, i, j, k, g;
vector<bool> prime(SIZE, true);
int main() {
  cin >> n;
  prime[0] = prime[1] = false;
  for (i = 2; i * i <= n; i++) {
    if (prime[i]) {
      for (j = i * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
  k = 0;
  while ((n - k) % 2 != 0) {
    for (i = 2; i <= n; i++) {
      if (prime[i]) {
        k = i;
        if ((n - k) % 2 == 0) break;
      }
    }
  }
  g = (n - k) / 2 + 1;
  if (n % 2 == 0) {
    g--;
  }
  cout << g << endl;
  ;
  for (i = 1; i <= (n - k) / 2; i++) {
    cout << 2 << " ";
    ;
  }
  if (n % 2) {
    cout << k;
  }
}

### Prompt

Develop a solution in Cpp to the problem described below:

Bachgold problem is very easy to formulate. Given a positive integer n represent it as a sum of maximum possible number of prime numbers. One can prove that such representation exists for any integer greater than 1.

Recall that integer k is called prime if it is greater than 1 and has exactly two positive integer divisors — 1 and k. 

Input

The only line of the input contains a single integer n (2 ≤ n ≤ 100 000).

Output

The first line of the output contains a single integer k — maximum possible number of primes in representation.

The second line should contain k primes with their sum equal to n. You can print them in any order. If there are several optimal solution, print any of them.

Examples

Input

5


Output

2
2 3


Input

6


Output

3
2 2 2

### Response

```cpp
#include <bits/stdc++.h>
const double PI =
    3.14159265358979323846264338327950288419716939937510582097494459230;
#pragma warning(disable : 4996);
using namespace std;
const long long inf = (long long)1e18 + 111;
const int iinf = (int)1e9 + 111;
const int SIZE = 1e5 + 11;
int n, i, j, k, g;
vector<bool> prime(SIZE, true);
int main() {
  cin >> n;
  prime[0] = prime[1] = false;
  for (i = 2; i * i <= n; i++) {
    if (prime[i]) {
      for (j = i * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
  k = 0;
  while ((n - k) % 2 != 0) {
    for (i = 2; i <= n; i++) {
      if (prime[i]) {
        k = i;
        if ((n - k) % 2 == 0) break;
      }
    }
  }
  g = (n - k) / 2 + 1;
  if (n % 2 == 0) {
    g--;
  }
  cout << g << endl;
  ;
  for (i = 1; i <= (n - k) / 2; i++) {
    cout << 2 << " ";
    ;
  }
  if (n % 2) {
    cout << k;
  }
}

```