← 返回题目列表

Codeforces · 449/C

C. Jzzhu 和苹果

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

Jzzhu 从他的大苹果树上摘了 n 个苹果。所有苹果都从 1 到 n 编号。现在他想把它们卖给一家苹果商店。

Jzzhu 会将他的苹果分组然后出售。每个组必须包含两个苹果,并且每个组中苹果数量的最大公约数必须大于1。当然,每个苹果最多可以属于一个组。

Jzzhu 想知道如何获得最大可能的组数。你能帮助他吗?

输入

单个整数 n (1 ≤ n ≤ 105),苹果的数量。

输出

第一行必须包含一个整数m,代表他可以获得的最大组数。接下来的 m 行中的每一行都必须包含两个整数——当前组中苹果的数量。

如果有多个最佳答案,您可以打印其中任何一个。

示例

输入 #1

6

输出 #1

2
6 3
2 4

输入 #2

9

输出 #2

3
9 3
2 4
6 8

输入 #3

2

输出 #3

0