Alice and cricket

0

0 votes
Problem

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

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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)

Editor Image

?