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 PYTHON3):

Solution:
n = int(input())
print(n // 2)
for i in range(n // 2 - 1):
    print(2 , end = " ")
if n % 2 == 0:
    print(2)
else:
    print(3)




#DDDDDDDDDD         RRRRRRRRRRRRRRR                  A                    GGGGGGGGGGG      OOOOOOO      NNNNNNN       NNNNNNN
#D:::::::::DDD      R::::::::::::::R                A:A                GGG::::::::::G    OO:::::::OO    N::::::N      N:::::N
#D::::::::::::DD    R:::::RRRRRR::::R              A:::A             GG:::::::::::::G  OO:::::::::::OO  N:::::::N     N:::::N
#DDD::::DDDDD:::D   RR::::R     R::::R            A:::::A           G::::GGGGGGGG:::G O::::::OOO::::::O N::::::::N    N:::::N
#  D::::D    D:::D    R:::R     R::::R           A:::::::A         G::::G       GGGGG O:::::O   O:::::O N:::::::::N   N:::::N
#  D::::D     D:::D   R:::RRRRRR::::R           A::::A::::A       G::::G              O::::O     O::::O N:::::N::::N  N:::::N
#  D::::D     D:::D   R:::::::::::RR           A::::A A::::A      G::::G    GGGGGGGGG O::::O     O::::O N:::::N N:::N N:::::N
#  D::::D     D:::D   R:::RRRRRR::::R         A::::A   A::::A     G::::G    G:::::::G O::::O     O::::O N:::::N  N:::N::::::N
#  D::::D     D:::D   R:::R     R:::R        A::::AAAAAAA::::A    G::::G    GGGGG:::G O::::O     O::::O N:::::N   N:::::::::N
#  D::::D    D:::D    R:::R     R::::R      A:::::::::::::::::A    G::::G       G:::G O:::::O   O:::::O N:::::N    N::::::::N
#DDD::::DDDDD:::D   RR::::R     R::::R     A::::AAAAAAAAAAA::::A    G::::GGGGGGGG:::G O::::::OOO::::::O N:::::N     N:::::::N
#D::::::::::::DD    R:::::R     R::::R    A::::A           A::::A    GG:::::::::::::G  OO:::::::::::OO  N:::::N      N::::::N
#D:::::::::DDD      R:::::R     R::::R   A::::A             A::::A     GGG:::::GGG::G    OO:::::::OO    N:::::N       N:::::N
#DDDDDDDDDD         RRRRRRR     RRRRRR  AAAAAA               AAAAAA       GGGGG   GGG      OOOOOOO      NNNNNNN       NNNNNNN
#
#
#
#
#   SSSSSSSSSSSSS  LLLLLLLLL                             A               YYYYYY     YYYYYY EEEEEEEEEEEEEEEE RRRRRRRRRRRRRR
# SS:::::::::::::S L:::::::L                            A:A              Y::::Y     Y::::Y E::::::::::::::E R:::::::::::::R
#S:::SSSSSS::::::S L:::::::L                           A:::A             Y::::Y     Y::::Y E:::EEEEEEEEE::E R:::::RRRRRR:::R
#S:::S     SSSSSSS LL:::::LL                          A:::::A            Y:::::Y   Y:::::Y   E:E       EEEE RR::::R     R:::R
#S:::S               L:::L                           A:::::::A           YYY::::Y Y::::YYY   E:E              R:::R     R:::R
# S::SSSS            L:::L                          A::::A::::A             Y::::Y::::Y      E:E              R:::RRRRRR:::R
#  SS::::SSSSS       L:::L                         A::::A A::::A             Y:::::::Y       E:EEEEEEE        R::::::::::RR
#    SSS::::::SS     L:::L                        A::::A   A::::A             Y:::::Y        E:EEEEEEE        R:::RRRRRR:::R
#       SSSSSS::S    L:::L                       A::::AAAAAAA::::A             Y:::Y         E:E              R:::R     R:::R
#            S:::S   L:::L                      A:::::::::::::::::A             Y::Y         E:E              R:::R     R:::R
#SSSSSSS     S:::S   L:::L         LLLLLL      A::::AAAAAAAAAAA::::A            Y::Y         E:E       EEEE RR::::R     R:::R
#S::::::SSSSSS:::S LL:::::LLLLLLLLL:::::L     A::::A           A::::A        YYYY::YYYY    E:::EEEEEEEE:::E R:::::R     R:::R
#S::::::::::::::SS LL:::::::::::::::::::L    A::::A             A::::A       Y::::::::Y    E::::::::::::::E R:::::R     R:::R
# SSSSSSSSSSSSSS   LLLLLLLLLLLLLLLLLLLLLL   AAAAAA               AAAAAA      YYYYYYYYYY    EEEEEEEEEEEEEEEE RRRRRRR     RRRRR