408725: GYM103274 C Cypher Decypher

The main enemies of democracy (the anti-democrats) have created a new encryption key for their texts, but it has been cracked! It is based on prime numbers, those that do not have divisors greater than 1.

This new encryption key is based on being able to find the number of primes in an interval of numbers. Anti-Democrats considered that having prime numbers up to one million was going to be enough to confuse the Allies. To prove them wrong, you have been tasked with breaking encrypted messages.

Given two numbers $$$i$$$, $$$j$$$, your task consists to count the number of prime numbers that are in the interval $$$[i, j]$$$ (including the extremes).

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5 $$$) Each of the next $$$T$$$ lines contains two integers separated by a space that defines the interval $$$[i, j]$$$ ($$$1 \leq i \leq j \leq 10^6$$$

For each test case in the input print a line with a single integer, the number of prime numbers that are in the interval (including the extremes) defined by the test case.

2
2 3
2 2

2
1