Micro and Prime Prime

3.8

524 votes
Approved, Data Structures, Easy, Hiring, Sieve
Problem

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:
1T105
1L,R106

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?