Count Prime Numbers in Ranges

You are given T test cases. Each test case contains two integers a and b. Your task is to count the number of prime numbers in the inclusive range \([a, b]\). If a is greater than b, the range is considered invalid and the answer is 0. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For more details, consider the prime counting function \(\pi(n)\), which represents the number of primes less than or equal to \(n\).

inputFormat

The first line of input contains an integer T denoting the number of test cases. Each of the following T lines contains two integers a and b, representing the start and end of the range, respectively.

outputFormat

For each test case, output a single line containing the count of prime numbers in the inclusive range ([a, b]).## sample

1
1 10

4