正整数 a 和 b 的最大公因数是满足 a,b 同时是 d 的倍数的最大的正整数 d。
而正整数 a 和 b 互质，指的是 a 和 b 的最大公因数为 1。
给定一个正整数 n，求最少把 1\sim n 共 n 个正整数分成多少堆，才能使得每一堆里面每两个数都互质。
一行一个正整数 n。
一行一个整数表示最少的堆数。
2
1
5
2
一种合法方案是把 1,2 放在同一堆，则 1,2 的最大公因数是 1，它们互质，所以满足要求。
一种合法方案是把 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}。