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.util.function.Function;

public class A_388_div2
{
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer stringTokenizer = null;
    private static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    private static String next() throws IOException
    {
        while ((stringTokenizer == null) || (!stringTokenizer.hasMoreTokens()))
        {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        }
        return stringTokenizer.nextToken();
    }

    public static int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }

    public static double nextDouble() throws IOException
    {
        return Double.parseDouble(next());
    }

    public static long nextLong() throws IOException
    {
        return Long.parseLong(next());
    }

    public static String nextLine() throws IOException
    {
        return bufferedReader.readLine();
    }

    public static void close()
    {
        out.close();
    }

    public static final long[] POWER2 = generatePOWER2();


    static class Array<Type> implements Iterable<Type>
    {
        private Object[] array;

        public Array(int size)
        {
            this.array = new Object[size];
        }

        public Array(int size, Type element)
        {
            this(size);
            Arrays.fill(this.array, element);
        }

        public Array(Array<Type> array, Type element)
        {
            this(array.size() + 1);
            for (int index = 0; index < array.size(); index++)
            {
                set(index, array.get(index));
            }
            set(size() - 1, element);
        }

        public Array(List<Type> list)
        {
            this(list.size());
            int index = 0;
            for (Type element: list)
            {
                set(index, element);
                index += 1;
            }
        }

        public Type get(int index)
        {
            return (Type)this.array[index];
        }
        public Array set(int index, Type value)
        {
            this.array[index] = value;
            return this;
        }

        public int size()
        {
            return this.array.length;
        }

        public List<Type> toList()
        {
            List<Type> result = new ArrayList<>();
            for (Type element: this)
            {
                result.add(element);
            }
            return result;
        }

        @Override
        public Iterator<Type> iterator()
        {
            return new Iterator<Type>()
            {
                int index = 0;

                @Override
                public boolean hasNext()
                {
                    return this.index < size();
                }

                @Override
                public Type next()
                {
                    Type result = Array.this.get(index);
                    index += 1;
                    return result;
                }
            };
        }
    }

    interface BiFunctionResult<Type0, Type1, TypeResult>
    {
        TypeResult apply(Type0 x0, Type1 x1, TypeResult x2);
    }

    static abstract class Edge<TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>>
    {
        public final TypeVertex vertex0;
        public final TypeVertex vertex1;

        public Edge(TypeVertex vertex0, TypeVertex vertex1, boolean bidirectional)
        {
            this.vertex0 = vertex0;
            this.vertex1 = vertex1;
            this.vertex0.edges.add(getThis());
            if (bidirectional)
            {
                this.vertex1.edges.add(getThis());
            }
        }

        private TypeVertex other(Vertex<TypeVertex, TypeEdge> vertex)
        {
            TypeVertex result;
            if (vertex0 == vertex)
            {
                result = vertex1;
            }
            else
            {
                result = vertex0;
            }
            return result;
        }

        public TypeVertex from(Vertex<TypeVertex, TypeEdge> to)
        {
            return other(to);
        }

        public TypeVertex to(Vertex<TypeVertex, TypeEdge> from)
        {
            return other(from);
        }

        public abstract TypeEdge getThis();
    }

    public static class EdgeDefault<TypeVertex extends Vertex<TypeVertex, EdgeDefault<TypeVertex>>> extends Edge<TypeVertex, EdgeDefault<TypeVertex>>
    {
        public EdgeDefault(TypeVertex vertex0, TypeVertex vertex1, boolean bidirectional)
        {
            super(vertex0, vertex1, bidirectional);
        }

        @Override
        public EdgeDefault<TypeVertex> getThis()
        {
            return this;
        }
    }

    public static class Vertex<TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>> implements Comparable<Vertex<? super TypeVertex, ? super TypeEdge>>
    {
        public final int index;
        public final List<TypeEdge> edges;

        public Vertex(int index)
        {
            this.index = index;
            this.edges = new ArrayList<>();
        }

        public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult depthFirstSearch(
                BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
                TypeVertex vertex,
                TypeEdge edge,
                TypeResult result,
                Array<Boolean> visited
        )
        {
            if (!visited.get(vertex.index))
            {
                visited.set(vertex.index, true);
                result = function.apply(vertex, edge, result);
                for (TypeEdge edgeNext: vertex.edges)
                {
                    TypeVertex vertexNext = edge.to(vertex);
                    result = depthFirstSearch(function, vertexNext, edgeNext, result, visited);
                }
            }
            return result;
        }

        public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult depthFirstSearch(
                Array<TypeVertex> vertices,
                int indexVertexStart,
                BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
                TypeResult result
        )
        {
            Array<Boolean> visited = new Array(vertices.size(), false);
            return depthFirstSearch(function, vertices.get(indexVertexStart), null, result, visited);
        }

        public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult breadthFirstSearch(
                TypeVertex vertex,
                TypeEdge edge,
                BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
                Array<Boolean> visited,
                LIFO<TypeVertex> verticesNext,
                LIFO<TypeEdge> edgesNext,
                TypeResult result
        )
        {
            if (!visited.get(vertex.index))
            {
                visited.set(vertex.index, true);
                result = function.apply(vertex, edge, result);
                for (TypeEdge edgeNext: vertex.edges)
                {
                    TypeVertex vertexNext = edgeNext.to(vertex);
                    if (!visited.get(vertexNext.index))
                    {
                        verticesNext.push(vertexNext);
                        edgesNext.push(edgeNext);
                    }
                }
            }
            return result;
        }

        public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult breadthFirstSearch(
                Array<TypeVertex> vertices,
                int indexVertexStart,
                BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
                TypeResult result
        )
        {
            Array<Boolean> visited = new Array(vertices.size(), false);
            LIFO<TypeVertex> verticesNext = new LIFO<>();
            verticesNext.push(vertices.get(indexVertexStart));
            LIFO<TypeEdge> edgesNext = new LIFO<>();
            edgesNext.push(null);
            while (!verticesNext.isEmpty())
            {
                result = breadthFirstSearch(verticesNext.pop(), edgesNext.pop(), function, visited, verticesNext, edgesNext, result);
            }
            return result;
        }

        @Override
        public int compareTo(Vertex<? super TypeVertex, ? super TypeEdge> that)
        {
            return Integer.compare(this.index, that.index);
        }
    }

    public static class VertexDefault<TypeEdge extends Edge<VertexDefault<TypeEdge>, TypeEdge>> extends Vertex<VertexDefault<TypeEdge>, TypeEdge>
    {
        public VertexDefault(int index)
        {
            super(index);
        }
    }

    public static class Tuple2<Type0, Type1>
    {
        public final Type0 v0;
        public final Type1 v1;

        public Tuple2(Type0 v0, Type1 v1)
        {
            this.v0 = v0;
            this.v1 = v1;
        }
    }

    public static class Tuple2Comparable<Type0 extends Comparable<? super Type0>, Type1 extends Comparable<? super Type1>> extends Tuple2<Type0, Type1> implements Comparable<Tuple2Comparable<Type0, Type1>>
    {
        public Tuple2Comparable(Type0 v0, Type1 v1)
        {
            super(v0, v1);
        }

        @Override
        public int compareTo(Tuple2Comparable<Type0, Type1> that)
        {
            int result = this.v0.compareTo(that.v0);
            if (result == 0)
            {
                result = this.v1.compareTo(that.v1);
            }
            return result;
        }
    }

    public static class SingleLinkedList<Type>
    {
        public final Type element;
        public SingleLinkedList<Type> next;

        public SingleLinkedList(Type element, SingleLinkedList<Type> next)
        {
            this.element = element;
            this.next = next;
        }

        public void toCollection(Collection<Type> collection)
        {
            if (this.next != null)
            {
                this.next.toCollection(collection);
            }
            collection.add(this.element);
        }
    }

    public static class LIFO<Type>
    {
        public SingleLinkedList<Type> start;
        public SingleLinkedList<Type> end;

        public LIFO()
        {
            this.start = null;
            this.end = null;
        }

        public void push(Type element)
        {
            SingleLinkedList<Type> list = new SingleLinkedList<>(element, null);
            if (this.start == null)
            {
                this.start = list;
                this.end = list;
            }
            else
            {
                this.end.next = list;
                this.end = list;
            }
        }

        public Type pop()
        {
            Type result = this.start.element;
            this.start = this.start.next;
            return result;
        }

        public boolean isEmpty()
        {
            return this.start == null;
        }
    }

    public static class MapCount extends TreeMap<Long, Long>
    {
        private int size;

        public MapCount()
        {
            this.size = 0;
        }

        public MapCount(Comparator<? super Long> comparator)
        {
            super(comparator);
        }

        public long add(Long key, Long delta)
        {
            long result;
            if (delta > 0)
            {
                Long value = get(key);
                if (value == null)
                {
                    value = delta;
                }
                else
                {
                    value += delta;
                }
                put(key, value);
                result = delta;
            }
            else
            {
                result = 0;
            }
            this.size += result;
            return result;
        }

        public long remove(Long key, Long delta)
        {
            long result;
            if (delta > 0)
            {
                Long value = get(key) - delta;
                if (value <= 0)
                {
                    result = delta + value;
                    remove(key);
                }
                else
                {
                    result = delta;
                    put(key, value);
                }
            }
            else
            {
                result = 0;
            }
            this.size -= result;
            return result;
        }

        public int size()
        {
            return this.size;
        }
    }

    public static class MapSet<TypeKey extends Comparable<? super TypeKey>, TypeValue> extends TreeMap<TypeKey, TreeSet<TypeValue>> implements Iterable<TypeValue>
    {
        private int size;
        private Comparator<? super TypeValue> comparatorValue;

        public MapSet()
        {
            this(null);
        }

        public MapSet(Comparator<? super TypeValue> comparatorValue)
        {
            super();
            this.size = 0;
            this.comparatorValue = comparatorValue;
        }

        public TypeValue firstValue()
        {
            TypeValue result;
            Map.Entry<TypeKey, TreeSet<TypeValue>> firstEntry = firstEntry();
            if (firstEntry == null)
            {
                result = null;
            }
            else
            {
                result = firstEntry.getValue().first();
            }
            return result;
        }

        public Iterator<TypeValue> iterator()
        {
            return new Iterator<TypeValue>()
            {
                Iterator<TreeSet<TypeValue>> iteratorValues = values().iterator();
                Iterator<TypeValue> iteratorValue = null;

                @Override
                public boolean hasNext()
                {
                    return iteratorValues.hasNext() || (iteratorValue != null && iteratorValue.hasNext());
                }

                @Override
                public TypeValue next()
                {
                    if (iteratorValue == null || !iteratorValue.hasNext())
                    {
                        iteratorValue = iteratorValues.next().iterator();
                    }
                    return iteratorValue.next();
                }
            };
        }

        public TypeValue lastValue()
        {
            TypeValue result;
            Map.Entry<TypeKey, TreeSet<TypeValue>> lastEntry = lastEntry();
            if (lastEntry == null)
            {
                result = null;
            }
            else
            {
                result = lastEntry.getValue().last();
            }
            return result;
        }

        public boolean add(TypeKey key, TypeValue value)
        {
            TreeSet<TypeValue> set = get(key);
            if (set == null)
            {
                if (comparatorValue == null)
                {
                    set = new TreeSet<>();
                }
                else
                {
                    set = new TreeSet<>(comparatorValue);
                }
                put(key, set);
            }
            boolean result = set.add(value);
            if (result)
            {
                this.size += 1;
            }
            return result;
        }

        public boolean remove(TypeKey key, TypeValue value)
        {
            boolean result;
            TreeSet<TypeValue> set = get(key);
            if (set == null)
            {
                result = false;
            }
            else
            {
                result = set.remove(value);
                if (set.size() == 0)
                {
                    remove(key);
                }
                if (result)
                {
                    this.size -= 1;
                }
            }
            return result;
        }

        @Override
        public int size()
        {
            return this.size;
        }
    }

    public static int binarySearchMinimum(Function<Integer, Boolean> filter, int start, int end)
    {
        int result;
        if (start == end)
        {
            result = end;
        }
        else
        {
            int middle = start + (end - start) / 2;
            if (filter.apply(middle))
            {
                result = binarySearchMinimum(filter, start, middle);
            }
            else
            {
                result = binarySearchMinimum(filter, middle + 1, end);
            }
        }
        return result;
    }

    public static int binarySearchMaximum(Function<Integer, Boolean> filter, int start, int end)
    {
        return -binarySearchMinimum(x -> filter.apply(-x), -end, -start);
    }

    public static long divideCeil(long x, long y)
    {
        return (x + y - 1) / y;
    }

    public static long faculty(int n)
    {
        long result = 1;
        for (int index = 2; index <= n; index++)
        {
            result *= index;
        }
        return result;
    }

    public static int gcd(int a, int b)
    {
        // TODO: slow
        int result = 1;
        int min = Math.min(a, b);
        int max = Math.max(a, b);
        for (int test = 2; result == 1 && test <= min; test++)
        {
            if (min % test == 0 && max % test == 0)
            {
                result *= test * gcd(min / test, max / test);
            }
        }
        return result;
    }

    public static long[] generatePOWER2()
    {
        long[] result = new long[63];
        for (int x = 0; x < result.length; x++)
        {
            result[x] = 1L << x;
        }
        return result;
    }

    public static int lcm(int a, int b)
    {
        return a * b / gcd(a, b);
    }

    public static <T> List<T> permutation(long p, List<T> x)
    {
        List<T> copy = new ArrayList<>();
        for (int index = 0; index < x.size(); index++)
        {
            copy.add(x.get(index));
        }
        List<T> result = new ArrayList<>();
        for (int indexTo = 0; indexTo < x.size(); indexTo++)
        {
            int indexFrom = (int) p % copy.size();
            p = p / copy.size();
            result.add(copy.remove(indexFrom));
        }
        return result;
    }

    public static <Type> void println(Iterator<Type> iterator)
    {
        if (iterator.hasNext())
        {
            out.print(iterator.next());
        }
        while (iterator.hasNext())
        {
            out.print(" " + iterator.next());
        }
        out.println();
    }

    public static <Type> void println(Iterable<Type> iterable)
    {
        println(iterable.iterator());
    }

    public static void main(String[] args)
    {
        try
        {
            solve();
        } catch (IOException exception)
        {
            exception.printStackTrace();
        }
        close();
    }

    public static int convert(int offset, boolean[] sieve, int[] primes, int primesCount)
    {
        for (int index = 0; index < sieve.length; index++)
        {
            if (sieve[index])
            {
                primes[primesCount] = offset + index;
                primesCount += 1;
            }
        }
        return primesCount;
    }

    public static boolean[] generateSieve(int size)
    {
        boolean[] result = new boolean[size];
        for (int index = 0; index < size; index++)
        {
            result[index] = true;
        }
        return result;
    }

    public static int[] generatePrimes(int n)
    {
        int[] primes = new int[(int) (n / Math.log(n) * 2)];
        int primesCount = 0;
        int segmentSize = (int) Math.sqrt(n);
        if (segmentSize * segmentSize < n)
        {
            segmentSize += 1;
        }
        int sqrt4 = (int) Math.sqrt(segmentSize);
        boolean[] sieve = generateSieve(segmentSize);
        sieve[0] = false;
        sieve[1] = false;
        for (int prime = 0; prime <= sqrt4; prime++)
        {
            if (sieve[prime])
            {
                for (int mul = 2; prime * mul < segmentSize; mul++)
                {
                    sieve[prime * mul] = false;
                }
            }
        }
        primesCount = convert(0, sieve, primes, primesCount);
        int primesCountSieve = primesCount;
        for (int segment = 1; segment < segmentSize; segment++)
        {
            sieve = generateSieve(segmentSize);
            int offset = segmentSize * segment;
            for (int indexPrime = 0; indexPrime < primesCountSieve; indexPrime++)
            {
                int prime = primes[indexPrime];
                for (int mul = offset / prime; prime * mul - offset < segmentSize; mul++)
                {
                    if (prime * mul - offset >= 0)
                    {
                        sieve[prime * mul - offset] = false;
                    }
                }
            }
            primesCount = convert(offset, sieve, primes, primesCount);
        }
        int[] result = new int[primesCount];
        for (int index = 0; index < primesCount; index++)
        {
            result[index] = primes[index];
        }
        return result;
    }

    public static void solve() throws IOException
    {
        int n = nextInt();
        if (n % 2 == 1)
        {
            out.println(n / 2);
            for (int index = 0; index < n / 2 - 1; index++)
            {
                out.print(2 + " ");
            }
            out.println(3);
        }
        else
        {
            out.println(n / 2);
            for (int index = 0; index < n / 2; index++)
            {
                out.print(2 + " ");
            }
            out.println();
        }

    }
}