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≤T≤105
1≤L,R≤106