D. Prime Counting
Tag(s):

## Greedy Algorithms, Math, Sieve

Problem
Editorial
Analytics

Deepjoy is very much fond of prime numbers. He is fascinated by the fact that these numbers are divisible by only $2$ numbers ($1$ and the number itself).

His friends challenged him with a problem related to the prime numbers which he eventually cracked.

Now its your turn to solve the problem. Lets see whether you can solve it or not!

You are given $N$ intervals in the form of $[l_i, r_i]$ (for each valid $i$, where $1 \le i \le N$). Each interval contains contains all the integers $x$ satisfying the condition $x \ge l_i, x \le r_i$. Now find the intersection of all the intervals (integers common to all the intervals) and print the count of the number of primes within the common intersection interval.

Input:

• First line: A single integer $T$ denoting the number of test cases
• Each test case contains the following lines:
• $1st$ line: $N$, the no. of intervals
• $N$ lines follow giving the intervals in the form of $l, r$

Output:

Print the count of prime nos. lying in the common interval (of all the $N$ intervals). If there is no common interval among the $N$ intervals, print $-1$.

Constraints:

$1 \le T \le 10$

$1 \le N \le 10$

$1 \le l_i \le r_i \le 10^9$

$1 \le r_i-l_i \le 10^5$

SAMPLE INPUT
2
2
2 10
5 19
2
2 3
6 100
SAMPLE OUTPUT
2
-1
Explanation

$1st$ test case:

The common interval is $[5,10]$. Now the prime nos. within this range are $5,7$. So the total prime nos. within this range is $2$.

Time Limit: 0,3 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...