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
3 7

-----Sample Output-----
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.

见题面

见题面