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