← 返回题目列表

AtCoder · abc084_d

D. 2017 年类似号码

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们说奇数 N is 与 2017 年类似 当两者 N 和 (N+1)/2 是素数。

你被给予 Q 查询。

在 i第一个查询,给定两个奇数 l_i 和 r_i,求奇数个数 x 与 2017 年类似,因此 l_i ≤ x ≤ r_i.

约束

  • 1≤Q≤10^5
  • 1≤l_i≤r_i≤10^5
  • l_i 和 r_i 是奇数。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

Q
l_1 r_1
:
l_Q r_Q

输出

打印 Q 行。的 i第行 (1≤i≤Q) 应包含对 i第一个查询。


示例输入 1

1
3 7

示例输出 1

2
  • 3 与 2017 年类似,因为 3 和 (3+1)/2=2 是素数。
  • 5 与 2017 年类似,因为 5 和 (5+1)/2=3 是素数。
  • 7 与 2017 年不相似,因为 (7+1)/2=4 不是素数,尽管 7 是质数。

因此,对第一个查询的响应应该是 2.


示例输入 2

4
13 13
7 11
7 11
2017 2017

示例输出 2

1
0
0
1

请注意 2017 也与2017年类似。


示例输入 3

6
1 53
13 91
37 55
19 51
73 91
13 49

示例输出 3

4
4
1
1
1
2