Happy Numbers Interval

You are given Q queries. For each query you are given three positive integers K, L, and M. Define the set of happy numbers as follows:

[ S = { x \mid x \le M \text{ or } x \text{ is a prime number} } ]

For each query, find the smallest positive integer i (with \(1 \le i \le 10^7\)) such that the interval \([i, i+K-1]\) contains exactly \(L\) numbers from S. If no such i exists within \(10^7\), output -1.

Note: A number \(x\) is considered happy if either \(x \le M\) or (if \(x > M\)) if \(x\) is a prime number.

inputFormat

The first line contains a positive integer \(Q\) indicating the number of queries. Each of the following \(Q\) lines contains three space-separated integers \(K\), \(L\), and \(M\).

Constraints:

• \(1 \le Q\)
• \(1 \le K, L, M\)
• Consider only \(i\) with \(1 \le i \le 10^7\).

outputFormat

For each query, output a single line containing the required integer i if it exists, otherwise output -1.

sample

1
5 3 3

2