/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 l_i,r_i が与えられるので、l_i≦x≦r_i かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
- 1≦Q≦10^5
- 1≦l_i≦r_i≦10^5
- l_i,r_i は奇数
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q l_1 r_1 : l_Q r_Q
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
入力例 1
1 3 7
出力例 1
2
-
3 も (3+1)÷2=2 も素数であるため、3 は 2017に似た数 です。
-
5 も (5+1)÷2=3 も素数であるため、5 は 2017に似た数 です。
-
7 は素数ですが、 (7+1)÷2=4 は素数ではないため、7 は 2017に似た数 ではありません。
よって、クエリ 1 の答えは 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
Score : 400 points
Problem Statement
We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.
You are given Q queries.
In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.
Constraints
- 1≤Q≤10^5
- 1≤l_i≤r_i≤10^5
- l_i and r_i are odd.
- All input values are integers.
Input
Input is given from Standard Input in the following format:
Q l_1 r_1 : l_Q r_Q
Output
Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.
Sample Input 1
1 3 7
Sample Output 1
2
- 3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.
- 5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.
- 7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.
Thus, the response to the first query should be 2.
Sample Input 2
4 13 13 7 11 7 11 2017 2017
Sample Output 2
1 0 0 1
Note that 2017 is also similar to 2017.
Sample Input 3
6 1 53 13 91 37 55 19 51 73 91 13 49
Sample Output 3
4 4 1 1 1 2