7046: Ladder
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：25
解决：15
题目描述
话说哪吒遇到了观音菩萨给他的考验，需要爬天梯，哪吒一开始在第$1$阶天梯上，他需要爬到第$r (1< r <= 10000000)$阶天梯。天梯上还有妖怪，如果一个天梯的阶数是质数，那么这天梯上就会有一个妖怪，哪吒认为，天梯前面一段的妖怪会比较多，准备使用风火轮飞过前面一部分，从第$l (1 < l <= r )$阶开始爬起（包括$l$阶上的怪物和r阶的怪物）。
你能告诉哪吒，现在他需要消灭多少只怪物吗？
你能告诉哪吒，现在他需要消灭多少只怪物吗？
输入
输入一个整数$T$，表示询问次数。$1<=T<=10000$
输入$T$行，每行两个整数，分别表示$l,r$。
输入$T$行，每行两个整数，分别表示$l,r$。
输出
输出$T$行，$T$个整数，表示他需要消灭的怪物数量。
样例输入 复制
1
2 20样例输出 复制
8