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

## This Problem was Asked in

Initializing Code Editor...