← 返回题目列表

Codeforces · 749/A

A. 巴赫戈尔德问题

中文机器翻译题面 查看原题

巴赫戈尔德问题很容易表述。给定一个正整数 n 将其表示为最大可能素数数之和。我们可以证明对于任何大于 1 的整数都存在这样的表示。

回想一下,如果整数 k 大于 1 并且恰好有两个正整数除数 — 1 和 k,则该整数 k 被称为素数。

输入

输入的唯一行包含单个整数 n (2 ≤ n ≤ 100 000)。

输出

输出的第一行包含一个整数 k — 表示中素数的最大可能数量。

第二行应包含 k 个质数,其总和等于 n。您可以按任何顺序打印它们。如果有多个最优解,则打印其中任意一个。

示例

输入 #1

5

输出 #1

2
2 3

输入 #2

6

输出 #2

3
2 2 2