100843: [AtCoder]ABC084 D - 2017-like Number
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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