408725: GYM103274 C Cypher Decypher

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Cypher Decyphertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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).

Input

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$$$

Output

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.

ExampleInput
2
2 3
2 2
Output
2
1

加入题单

上一题 下一题 算法标签: