题目描述

薯条哥想构造一个长度为 $n$ 的数组$\left \{a_1,a_2,...,a_n \right \}$，其中 $a_i$ 满足 $1\le a_i \le n$ ，$[1,n]$ 的每个数字可以重复使用也可以不用。

他希望任意两个索引 $i,j$ 满足 $(i\ne j$ 且 $gcd(i,j)\ne 1)$ 时，其两个位置的权值不相等，即 $a_i \ne a_j$ ，

请你帮助薯条哥判断最少需要多少种不同的数字。

输入描述

输入一个整数 $n(1 \le n \le 10^9)$ ，表示薯条哥希望你构造的数组长度。

输出描述

输出一个整数，表示数组中不同数字的个数的最小值。

样例1

输入

3

输出

1

样例解释

数组下标依次为 $[1,2,3]$ ，对于任意的两个索引$i,j(i \ne j)$ 都满足 $gcd(i,j) = 1$ ，

所以我们可以只使用 $2$ 来填数组 ，为 $[2,2,2]$，当然 $[1,1,1]$ 或者 $[3,3,3]$ 也是正确的。

样例2

输入

4

输出

2