All Tracks Math Number Theory Primality Tests Problem

Micro and Prime Prime
Tag(s):

Data Structures, Easy, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

nuVizz

Challenge Name

nuVizz Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications