问题描述

小达最近学习了如何判断一个数是否是质数，他写出了一个判断质数的函数。不过，他发现这个函数存在缺陷，会对某些数给出错误的结果。现在，小达想统计在给定范围 $1,2,3,…,n$ 内，有多少个数会让这个函数返回错误的结果（即输入质数时返回 $false$，或者输入非质数时返回 $true$ ）。

bool isprime(long long n){
	if(n<=1) return false;
	for(long long i=2;i*i<n;i++){
		if(n%i==0){
			return false;
		}
	}
	return true;
}

例如，当 $n= 9$ 时，这个函数会错误地返回 $true$（因为 $i*i < 9$ 的循环条件，$i$ 只会遍历到 $2$，无法检测到 $9=3×3$ ，导致误判为质数 ）。

输入格式

输入一个正整数 $n$ ，表示需要检测的数字范围上限。

输出格式

输出一个整数，表示在 $1,2,3,…,n$ 中，让该函数返回错误结果的数字个数。

样例输入

100

样例输出

4

数据范围

对于 $30\%$ 的数据， $1 \leq n \leq 100000$

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

对于全部的数据， $1 \leq n \leq 10^{14}$