题目描述

戴维·希尔伯特是 20 世纪初的一位伟大的数学家和教育学家。他曾经建议数学界对形如 $4\times x+1$ 的正整数（$x$ 是非负整数）进行研究。本题的背景是其中的一个研究。

我们把形如 $4\times x+1$ 的正整数（$x$ 是非负整数）成为 H 数。易得 H 数对乘法封闭。

两个 H 数相乘的积也一定是个 H 数，所以称 H 数对乘法封闭。

关于 H 数，也有一些衍生概念：

1. H 质数，即当这个数要表示成两个 H 数相乘的积的形式时只有 $1$ 种方案的情况（即 $1$ 和它自己的积），如 $5,9,13$（注意 $9$ 不是质数，但是是 H 质数）。
2. H 合数，即 H 数中除了 H 质数之外的其他数，如 $125$。
3. H 半质数，即 H 合数中 刚好 可以表示为 两个 H 质数 的积的数，如 $25 = 5^2$。$125$ 则不是，因为它可以表示为 $5^3$，也就是三个 H 质数的积。

现在给你一个 H 数 $n$。你需要输出 $1\sim n$ 之间有多少个 H 半质数。

提示：根据欧拉筛法求质数/合数的原理，来准确地筛选出所有的 H-半质数吧

输入格式

输入可能有很多行，且一定以一个数字 $0$ 结尾。

除了最后一行 $0$ 之外，其余每一行都为一个 H 数 $n$。

输出格式

对于每一行，输出对应询问的结果。

21 
85
789
0

0
5
62

数据规模与约定

对于 $100\%$ 的数据，保证 $n\le 10^6+1$。