Problem Description

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

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

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

Input Format

一行一个正整数 $n$。

Output Format

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

2

1

5

2

Hint

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

数据规模与约定

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

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

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