human
Write me a Python code to print them in any order given the following:
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
Using python3 can you solve the prior task?
assistant
#Here is Python code to print them in any order.

from collections import defaultdict

class PrimeCounter(object):

    def __init__(self, number):
        self.number = number
        self.counter = defaultdict(int)
        self.summary = list()

    def count(self, prime):
        self.counter[prime] += 1
        self.number -= prime
        self.summary.append(prime)

    def undo(self, prime):
        self.counter[prime] -= 1
        self.number += prime
        self.summary.pop()

    def get_summary(self):
        return len(self.summary), self.summary

def get_primes(n):
    """Returns  a list of primes < n.
    
    Source: http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
    """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

def greedy(number):
    """
    Compute primes.
    Fill in as much primes as we can - starting from the smallest.
    We don't need prime above 3, but we compute it anyway for the sake of greediness.
    """
    primes = sorted(get_primes(number + 1))
    i = 0
    count = defaultdict(int)
    pc = PrimeCounter(number)
    while pc.number > 0:
        # pickup smallest number if it fits
        prime = primes[i]
        if prime <= pc.number:
            pc.count(prime)
        else:
            pc.undo(prime)
            i += 1
    return pc.get_summary()

def number_theory(number):
    if number % 2 == 0:
        max_count = number // 2
        return max_count, [2] * max_count
    max_count = (number - 3) // 2
    return max_count + 1, ([2] * max_count) + [3]

def solve(number):
    """
    If we are looking for a maximum number of primes numbers that sums to a given number,
    we should use as many lowest prime number as we can.
    Any even number can be made with 2(lowest prime).
    Any odd number can be summed using a single 3 and 2s.
    """
    # return number_theory(number)
    return greedy(number)

def main():
   ...