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.
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$$
Print the number of Prime Prime Numbers for each between $$L$$ and $$R$$ for each test case in a new line.
$$ 1 \le T \le 10^5$$
$$ 1 \le L, R \le 10^6$$