SOLVE
LATER
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.
The first line of input contains one positive integer Q. The following Q lines contains three spaced-separated integers A, B and K.
For each query, print the answer in a new line, if it exists, else print 1.
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].