Yogesh And Primes Problem Statement

Yogesh, a bright student interested in Machine Learning research, must pass a test set by Professor Peter. To do so, Yogesh must correctly answer Q questions where each question provides three positive integers: A, B, and K, with the condition A ≤ B.

Yogesh needs to find an integer P such that P is as close as possible to A and there are at least K prime numbers in the range [A, P], where A ≤ P ≤ B.

Please find and print the minimum possible P or print -1 if no such integer exists.

Example:

Input:

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

Output:

Print the answer for each query on a new line, or -1 if not possible.

Constraints:

• 1≤Q≤100,000
• 1≤A≤B≤1,000,000
• 1≤K≤1,000,000
• A≤P≤B