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