Breaking Primes
Tag(s):

## Binary Search, Easy-Medium, Math, Sieve

Problem
Editorial
Analytics

Jesse Pinkman loves Maths. He loves prime numbers and wants to research on this topic. He asks his Maths professor Walter White a.k.a. Heisenberg for guidance. Heisenberg says that he will guide him if and only if he answers all his Q questions correctly. In all the Q questions, he gives three positive integers A, B and K where $A ≤ B.$

He asks Jesse to find an integer P closest to A such that there are at least K prime numbers in the range $[A, P]$ where $A ≤ P ≤ B$. Jesse needs your help as he is very interested to do research under Heisenberg. Find the minimum P or report 1 if there is no such P which meets the constraints.

Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

## Input format:

The first line of input contains one positive integer Q. The following Q lines contains three spaced-separated integers A, B and K.

## Output format:

For each query, print the answer in a new line, if it exists, else print 1.

## Constraints:

• $1 ≤ Q ≤ 100,000$
• $1 ≤ A ≤ B ≤ 1,000,000$
• $1 ≤ K ≤ 1,000,000$
• $A ≤ P ≤ B$
SAMPLE INPUT
5
2 5 1
2 5 2
4 12 2
3 17 7
5 5 1

SAMPLE OUTPUT
2
3
7
-1
5

Explanation

In the first query, 2 itself is a prime. So P=2.

In the second query, 3 is the minimum integer such that [2,3] contains 2 primes.

In the fourth query, there are only 6 prime numbers in the range [3,17].

Time Limit: 1.0 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: 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, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Honeywell Android Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching