分数: 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