You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

秋山澪(Mio)是樱高轻音部的电贝斯手及合唱(有时也会担任主唱),是一个左撇子,眼角稍稍挑起,有着到腰长度的黑发,是轻音部中唯一有后援会的部员.

当然Mio还是一个品学兼优的好学生,最近Mio突然对离散数学非常感兴趣,经过一段时间的研究Mio成功发现了偏序集中极小元的秘密,对此Mio非常高兴,迫不及待地向琴吹紬(Mugi)炫耀了自己的成果.作为Mio的好姐妹,Mugi也想研究离散数学,你能帮帮她吗?

Description

给定一个由正整数组成的集合$A$,他与整除关系 $R$ 构成一个偏序集 $<A,R>$。元素 $x \in A,y \in A$ , 若 $x$ 与 $y$ 满足 $x$ 整除$y$ 或 $y$ 整除 $x$, 则称 $x$ 与 $y$ 有关系.

若 $k$ 在所有与他有关系的元素所构成的集合 $B_k$ 中是最小的,则称 $k$ 为 $<A,R>$ 的极小元.

例如: $A$ 为 ${2,3,5,6,24,25}$,则 $B_6$ 为 ${2,3,6,24}$, 可以看出 $6$ 不是 $B_6$ 中最小元,所以 $6$ 不为极小元。$B_5$ 为 ${5,25}$, 所以 $5$ 为极小元.

给出的整数集$A$是个排除1的排列,求 $<A,R>$ 这个偏序集的极小元的个数.

换句话说，集合 $A$ 是 $\{2,3,4 \dots n+1\}$.

排列: 若一个长度为 $n$ 的正整数集包含所有不大于$n$ 的正整数,那他就是一个排列。例如 ${5,3,4,2,1}$ 是一个排列; ${2,3,3,4}$ 不是个排列,因为3出现了两次而1没有出现.

Format

Input

一个整数$n(1 \le n \le 10^7)$表示集合的大小.

Output

一个整数，表示极小元的个数。

Samples

5

3

11

5

Tips

对于第一个测试点来说集合$A$为{2,3,4,5,6},其中2,3,5为极小项.

Limitation

600ms, 256mb for each test case.