众所周知，质数指的是恰好只有两个不同的正整数因数的正整数。相似的，如果一个正整数t恰好只有三个不同的正整数因数，那么我们将t称之为T-质数。
现在给定若干组正整数l,r，对于每组l,r，请你求出对于所有的正整数x(l≤x≤r)，有多少个x满足x是T-质数。
第一行一个整数T，表示测试数据的组数。
对于每组测试数据：
一行用空格隔开的两个整数l,r，如题目描述中表示的含义。
对于每组测试数据：
一行一个整数表示答案。
2
2 10
1 1000000000000
2
78498
【样例解释】
对于样例1，在2,3,4,5,6,7,8,9,10中，只有4和9是T-质数，所以答案为2。
【数据范围及约定】
|
测试点编号
|
T≤
|
l,r≤
|
|
1~5
|
10
|
100
|
|
6~10
|
100
|
3×104
|
|
11~14
|
109
|
|
|
15~18
|
10
|
1012
|
|
19~20
|
105
|
对于100%的数据，T≤105，1≤l≤r≤1012