All Tracks Math Number Theory Primality Tests Problem

Micro and Prime Prime
/

Data Structures, Sieve

Problem
Editorial
Analytics

Micro just learned about prime numbers. But he quickly got bored of them, so he defined a new kind of numbers and called them Prime Prime Numbers. A number X is Prime Prime if number of prime numbers from 1 to X (inclusive) are prime. Now he wants to find out the number of Prime Prime numbers from L to R (inclusive). Help Micro with it.

Input:
First line consists of a single integer T denoting number of test cases
Following T lines consists of two space separated integers denoting L and R

Output:
Print the number of Prime Prime Numbers for each between L and R for each test case in a new line.

Constraints:
\( 1 \le T \le 10^5\)
\( 1 \le L, R \le 10^6\)

SAMPLE INPUT
2
3 10
4 12
SAMPLE OUTPUT
4
5
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?