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.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.lang.*;
import java.math.BigInteger;
public class me {

public static void main(String []args)
    {
		Scanner br=new Scanner(System.in);
        int n=br.nextInt();
        if(n%2==0)
        {
            int num=n/2;
            System.out.println(num);
            for(int i=0;i<num;i++)
            System.out.print("2"+" ");
        }else
        {
             int num=(n-1)/2;
              System.out.println(num);
            for(int i=0;i<num-1;i++)
            System.out.print("2"+" ");
            System.out.print("3");
        }
        
        
    }
    
            
    
    
         
    public static long  ways(int n, int r, long MOD)
    {
      //  vector<long long> f(n + 1,1);
        long f[]=new long[n+1];
        Arrays.fill(f,1);
        for (int i=2; i<=n;i++)
            f[i]= (f[i-1]*i) % MOD;
        return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
    }  
    
                  
                  
                  
                   /*THIS IS FOR THE INVERSE EULER*/
    public static long  InverseEuler(long n, long MOD)
    {
        return pow(n,MOD-2,MOD);
    }
    
    
    
                   
                   /*THIS ID THE CHECK FOR THE PRIME*/
    static int isPrime(int n) {
    for(int i=2;i<n;i++) {
        if(n%i==0)
            return 0;
    }
    return 1;
}
    
    
    
                          /*TO CHECK FOR THE GCD IN LONG*/
public static long gcd(long x,long y)
{
    if(x%y==0)
        return y;
    else
        return gcd(y,x%y);
}
    
    
    
                             /* CHECK FOR THE GCD IN INT*/
public static int gcd(int x,int y)
{
    if(x%y==0)
        return y;
    else 
        return gcd(y,x%y);
}


                         /*CHECK FOR THE ABSOLUTE IN INT*/
public static int abs(int a,int b)
{
    return (int)Math.abs(a-b);
}



                        /*CHECK FOR THE ABSOLUTE IN LONG*/
public static long abs(long a,long b)
{
    return (long)Math.abs(a-b);
}


                       /*CHECK FOR MAX BETWEEN TWO NUMBERS IN INT*/
public static int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}



                       /*CHECK FOR MIN BETWEEN TWO NUMBERS IN INT*/
public static int min(int a,int b)
{
    if(a>b)
        return b;
    else 
        return a;
}


                       /*CHECK FOR MAX BETWEEN TWO NUMBERS IN LONG*/
public static long max(long a,long b)
{
    if(a>b)
        return a;
    else
        return b;
}

                     /*CHECK FOR MIN BETWEEN TWO NUMBERS IN LONG*/
public static long min(long a,long b)
{
    if(a>b)
        return b;
    else 
        return a;
}
                    /*check for power of two of any num*/
static boolean isPowerOfTwo (long v) {
    return (v & (v - 1)) == 0;
}
public static long pow(long n,long p,long m)
{
     long  result = 1;
      if(p==0)
        return 1;
    if (p==1)
        return n;
    while(p!=0)
    {
        if(p%2==1)
            result *= n;
        if(result>=m)
        result%=m;
        p >>=1;
        n*=n;
        if(n>=m)
        n%=m;
    }
    return result;
}

                    /*SORT GIVEN ARRAY*/
static long sort(int a[],int n)
{   int b[]=new int[n]; 
    return mergeSort(a,b,0,n-1);}


static long mergeSort(int a[],int b[],long left,long right)
{ long c=0;if(left<right)
 {   long mid=left+(right-left)/2;
     c= mergeSort(a,b,left,mid);
     c+=mergeSort(a,b,mid+1,right);
     c+=merge(a,b,left,mid+1,right); }  
    return c;    }


static long merge(int a[],int  b[],long left,long mid,long right)
{long c=0;int i=(int)left;int j=(int)mid; int k=(int)left;
while(i<=(int)mid-1&&j<=(int)right)
{ if(a[i]<=a[j]) {b[k++]=a[i++]; }
else    { b[k++]=a[j++];c+=mid-i;}}
while (i <= (int)mid - 1)   b[k++] = a[i++]; 
while (j <= (int)right) b[k++] = a[j++];
for (i=(int)left; i <= (int)right; i++) 
    a[i] = b[i];  return c;  }


    
    
                       /*REMOVE ZERO FROM GIVEN NUM*/
static int removeZero(int num) {
        int ret = 0;
        int ten = 1;
        while (num>0) {
                int dig = num % 10;
                num /= 10;
                if (dig>0) {
                        ret += dig * ten;
                        ten *= 10;
                }
        }
        return ret;
}
                 /*CHECK FOR LCM*/
 static int lcm(int x, int y)
    {
        int a;
        a = (x > y) ? x : y; // a is greater number
        while(true)
        {
            if(a % x == 0 && a % y == 0)
                return a;
            ++a;
        }	
    }
}