问题描述

话说哪吒遇到了观音菩萨给他的考验，需要爬天梯，哪吒一开始在第$1$阶天梯上，他需要爬到第$r (1< r <= 1000000)$阶天梯。天梯上还有妖怪，如果一个天梯的阶数是质数，那么这天梯上就会有一个妖怪，哪吒认为，天梯前面一段的妖怪会比较多，准备使用风火轮飞过前面一部分，从第$l (1 < l <= r )$阶开始爬起（包括$l$阶上的怪物和r阶的怪物）。

你能告诉哪吒，现在他需要消灭多少只怪物吗？

输入输出格式

输入格式

输入一个整数$T$，表示询问次数。$1<=T<=10000$

输入$T$行，每行两个整数，分别表示$l,r$。

输出格式

输出$T$行，$T$个整数，表示他需要消灭的怪物数量。

测试样例

1
2 20

8

提示

对于30%的数据，$(1< r <= 10000)$，$1<=T<=10$

对于60%的数据，$(1< r <= 100000)$，$1<=T<=10000$

对于100%的数据，$(1< r <= 10000000)$，$1<=T<=10000$