某某群 里的复读机越来越多啦,每天都会进行很多次复读。
对此,秦皇发出铁令:如果有复读机不听话随意复读,就会被拖出去做成炒饭。
“秦皇不要啊!”
“不要啊!”
“啊!”
——来自一名可怜的复读机临终三连
可是,人类的本质就是复读,作为一名复读机,实在忍受不了不复读的憋屈。
他们多方打听,发现如果每个小组中复读机的编号两两互素(或者只有一个复读机),那么就能作为一个集体进行一条复读而不被禁言。
但是秦皇很严格,说假如复读机们不能尽可能最小化所分的组数,就发起一起大清洗,把所有的复读机都做成炒饭。
复读机们感到十分不安,于是他们想知道他们可以被分成几组进行复读,从而既可以避免被做成炒饭,又可以享受到复读的快乐。(当然现在,之前的炒饭全都成了兵马俑)
Standard Input
一个正整数N,表示复读机有N个,且复读机顺序编号为1至N中的自然数,1 <= N <=100,000。
Standard Output
一行,每有一组复读机复读一次Wed.Strong