Problem: 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

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.util.stream.*;

public class Main{
	private static BufferedReader in;
	private static BufferedWriter out;
	
	public static void main(String[] args) throws IOException {
		open();

		StringTokenizer st;
		StringBuilder sb;
	
		int n=readInt();
		int cont=0;
		String dos="2 ";
		if(n%2==0) {
			cont=n/2;
			out.write(cont+"\n");
			for(int i=0;i<cont;i++)
				out.write(dos);
			out.write("\n");
		}else{
			if(n==3)
				out.write("1\n3\n");
			else {
				cont=n/2;
				out.write(cont+"\n");
				for(int i=0;i<cont-1;i++)
					out.write(dos);
				out.write("3\n");
			}
		}
		
		close();
	}
	
	private static int[] readInts() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
	}
	private static int readInt() throws IOException {
		return Integer.parseInt(in.readLine());
	}
	private static long[] readLongs() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
	}
	private static long readLong() throws IOException {
		return Long.parseLong(in.readLine());
	}
	private static double[] readDoubles() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToDouble(Double::parseDouble).toArray();
	}
	private static double readDouble() throws IOException {
		return Double.parseDouble(in.readLine());
	}
	private static String readString() throws IOException {
		return in.readLine();
	}
	private static int setBit(int S, int j) {
		return S | (1 << j);
	}
	private static int isOn(int S, int j) {
		return S & (1 << j);
	}
	private static int clearBit(int S, int j) {
		return S & ~(1 << j);
	}
	private static int toggleBit(int S, int j) {
		return S ^ (1 << j);
	}
	private static int lowBit(int S) {
		return S & (-S);
	}
	private static int setAll(int n) {
		return (1 << n) - 1;
	}
	private static int modulo(int S, int N) {
		return ((S) & (N - 1));
	} // returns S % N, where N is a power of 2
	private static boolean isPowerOfTwo(int S) {
		return (S & (S - 1)) == 0 ? true : false;
	}
	private static int nearestPowerOfTwo(int S) {
		return ((int) Math.pow(2.0, (int) ((Math.log((double) S) / Math.log(2.0)) + 0.5)));
	}
	private static int turnOffLastBit(int S) {
		return ((S) & (S - 1));
	}
	private static int turnOnLastZero(int S) {
		return ((S) | (S + 1));
	}
	private static int turnOffLastConsecutiveBits(int S) {
		return ((S) & (S + 1));
	}
	private static int turnOnLastConsecutiveZeroes(int S) {
		return ((S) | (S - 1));
	}
	private static void open() {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new BufferedWriter(new OutputStreamWriter((System.out)));
	}
	private static void close() throws IOException {
		out.flush();
		out.close();
		in.close();
	}
}