题目描述

欧拉函数是数论中一个基本的函数，它是：对正整数n，小于或等于n的正整数中与n互质的数的数目，用φ(n)表示。（两个数的最大公约数为1，称为互质，因此 φ(1)=1）。 
例如φ(8)=4，因为1,3,5,7均和8互质。 

输入格式

一行一个整数n（n<=1000000） 。

输出格式

第一行一个整数φ(n)。
第二行若干个整数，从小到大输出与n互质的整数

样例数据

input

8

output

4
1 3 5 7