时间限制：1秒　　内存限制：256M

---

【问题描述】

　　请用“筛选法” 生成 \(1\) 到 \(5×10^6\) 内素数表函数；

　　然后实现查询：\(a\ b\)，表示查询区间 \([a,b]\) 内素数的个数，其中 \(1≤a≤b≤10^7\)。

【输入格式】

　　有若干行，每行包含两个正整数：\(a\ b\)，表示依次查询。

【输出格式】

　　对于每个询问，输出一个整数，表示查询结果。

【输入输出样例】

　Input

5 20
1 100
10000 5000000

　Output

6
25
347284

【数据限制】

　　对于 \(50\%\) 的数据，询问数不超过100次。
　　对于 \(100\%\) 的数据：询问数不超过100000次。

【来源】

　Mr.he