Description

小明发现2017是一个很特别的奇数，2017是一个质数，(2017+1)/2的结果1009也是一个质数。如果一个奇数n，它和2017一样，它本身是一个质数，(n+1)/2的数也是一个质数的话，就把它称为2017的相似数。小明想知道，从数字l到数字r中，有多少个2017的相似数？

Input Format

第一行为一个整数t，表示询问区间的个数。

接下来t行，每行两个整数l和r，表示询问的区间。

对于40%的数据保证：t<=10^3，1<=l<=r<=10^3。

对于100%的数据保证：t<=10^5，1<=l<=r<=10^6。

请使用较快的输入输出，如scanf、printf、使用\n而不是endl来换行。

Output Format

t行，每行一个整数，表示2017的相似数的数目。

1
3 7

2

Hint

样例解释：

3和5是2017的相似数，它们都满足本身是质数和(n+1)/2是质数的条件。7虽然是质数，但(7+1)/2=4不是质数，因此7不是2017的相似数。

Source

佛山市青少年科技素养创意挑战赛 六年级模拟题