Alice and Bob love to watch cricket. One day while watching a match India was in a critical situation. So, they both were predicting the match contradicting each other. According to Bob, Alice is bad with the calculations and his prediction is right. So he gives her a task to prove himself right.
He will provide a starting and ending value that describes a range of integers, inclusive of the endpoints. Alice must determine the number of prime integers within that range.
Can you help Alice in finding the answer?
Note- A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.
Input Format
The first line contains q, the number of test cases.
Each of the next lines contains two space-separated integers, a and b, the starting and ending integers in the ranges.
Output Format
Output q lines, where ith line represents the count of prime numbers between a and b(inclusive).
Constraints
1<=q<=100
0<=a<=b<=10^6
between 1 and 10: there are 4 primes (2,3,5,7)
between 2 and 3: there are 2 primes (2,3)
between 100 and 102: there is 1 prime (101)