T260249 横渡星河

大河向东流，天上的星星星星星星。——《华润风月鉴》

DD 和 XX 来到了星河前。 河中有 $n$ 块石头，名字为小1，2，……，$n$ ，他们不喜欢被踩过与自己名字互素的石头的脚碰自己,也就是说想要从互素的石头 $A$ 跳到 $B$ 就会被甩到河里，然而这些石头有让人实力大增的能力，所以 DD 和 XX 希望你告诉他们最多能踩过多少块石头而不掉进水里过河。

一行一个整数 $n$，表示一共有 $n$ 块石头。

一行一个整数 ，表示最多踩到石头个数。

样例一解释：由于1、2和3互素，所以最多选1、2和 3中的一个。 对于10%的数据，1