D - 2017-like Number

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

N(N+1)÷2 も素数」を満たす奇数 N2017に似た数 とします。

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 も素数であるため、32017に似た数 です。

  • 5(5+1)÷2=3 も素数であるため、52017に似た数 です。

  • 7 は素数ですが、 (7+1)÷2=4 は素数ではないため、72017に似た数 ではありません。

よって、クエリ 1 の答えは 2 個です。


入力例 2

4
13 13
7 11
7 11
2017 2017

出力例 2

1
0
0
1

20172017に似た数 であることに注意してください。


入力例 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