题目大意
给定正整数 n，要构造长度为 n 的数组 a[1..n]，每个元素取自 1..n，可重复使用。要求对于任意 i≠j 且 gcd(i,j)>1 的一对下标，必须满足 a[i]≠a[j]。问最少需要多少种不同的数字。

思路

1. 把下标 1…n 看成图的顶点，若 gcd(i,j)>1 则顶点 i、j 之间连边。

题目内容

小红想构造一个长度为 $n$ 的数组 ${a_1,a_2,….,a_n}$，其中 $a$ 满足 $1≤ a_i ≤ n$，$[1,n]$ 的每个数字可以重复使用也可以不用。

她希望任意两个索引 $i,j$ 满足 ($i≠ j$ 且 $gcd(i,j)≠1$ )时，其两个位置的权值不相等，即 $a_i ≠ a_j$ ，请你帮助小红判断最少需要多少种不同的数字。

输入描述

一个整数 $n(1 ≤ n ≤ 10^9)$ ，表示小红希望你构造的数组长度。

输出描述

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

样例1

输入

3

输出

1

说明

数组下标依次为 $[1,2,3]$ ，对于任意的两个索引 $i,j(i ≠ j)$ 都满足 $gcd(i,j)= 1$ ，所以我们可以只使用 $2$ 来填数组 ，为 $[2,2,2]$ ，当然 $[1,1,1]$ 或者 $[3,3,3]$ 也是正确的。

样例2

输入

4

输出

2