正整数 a 和 b 的最大公因数是满足 a,b 同时是 d 的倍数的最大的正整数 d。

而正整数 a 和 b 互质，指的是 a 和 b 的最大公因数为 1。

给定一个正整数 n，求最少把 1\sim n 共 n 个正整数分成多少堆，才能使得每一堆里面每两个数都互质。

一行一个正整数 n。

一行一个整数表示最少的堆数。

样例 1 解释

一种合法方案是把 1,2 放在同一堆，则 1,2 的最大公因数是 1，它们互质，所以满足要求。

样例 2 解释

一种合法方案是把 1,2,5 放在同一堆，3,4 放在同一堆，可以验证是满足要求的

数据规模与约定

对于 50\% 的数据，1\leq n\leq 10。

对于 70\% 的数据，1\leq n\leq 10^3。

对于 100\% 的数据，1\leq n\leq 10^{18}。