质数质数质数，到底有多少个质数？
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

这一天 xmy 很烦恼，他的数论很差，但是校赛题怎么能没有数论题呢？
哪怕出个最经典的数论题，当算法签到也好。
这时候他想到了质数。
那就考考你们 [A,B] 范围内，有多少个质数吧。
只回答一次就太无聊了，那就问答 N 次吧；

输入描述:

第一行一个整数 N 。
1\leq N \leq 10^{5}
以下N行，每行两个整数  。
1 \leq A \leq B \leq 10^{7}

输出描述:

输出 [A,B] 范围内，有多少个质数。
示例1

输入

复制 
10
1 1000000
1999 199999
666 66666
1 10
2 8
2 20
3 30
2 133
2 2333
2333 23333

输出

复制 
78498
17682
6524
4
4
8
9
32
345
2258