bee 3345 - Ferdinaccis Hobby

Ferdinacci is a somewhat different boy. On his computer he keeps a single file with all the prime numbers from 1 to a million (10⁶).

Among one of his hobbies, he usually spends hours and hours enjoying the beauty of prime numbers. He has looked at this list so long that he believes he has memorized it. To test his memory, damn Ferdinacci decided to apply the following test:

Choose an interval [L, R] within the file limits
Choose a K value
Find out which is the Kth prime within the chosen range

Ferdinacci intends to guess this "Kth" number based solely on his memory, but an algorithm is needed to check if he got the right guess.
To test memory for real, he plans to repeat the test Q times.

Input

In the first line, the integer Q is passed, representing the number of tests that Ferdinacci will do. In the next Q rows there will be three integers L, R and K in each row.

The restrictions for the values are as follows:

\(1 \leq \textbf{Q} \leq 10^5\)
\(1 \leq \textbf{L} \leq \textbf{R} \leq 10^6\)
\(1 \leq \textbf{K} \leq 10^6\)

Output

For each Ferdinacci test it is necessary to print an integer representing the "Kth" prime of the interval [L, R] (limits included).

If the "Kth" prime is outside the range [L, R] (limits included) it must print -1.

Input Sample	Output Sample
2 1 1000000 78498 1 10 5	999983 -1

Input Sample

Output Sample

1 1000000 78498

1 10 5

999983

-1