Problem Description

Given $Q$ queries, each providing positive integers $K, L, M$. Define the set of happy numbers as $\{x | x \le M$ or $x$ is a prime number$\}$.

For each query, find a positive integer $i$ such that the interval $[i, i+K-1]$ contains exactly $L$ happy numbers. If no such $i$ exists within $10^7$, output $-1$.

Input Format

The first line contains an integer $Q$.

The next $Q$ lines each contain three integers $K_i, L_i, M_i$.

Output Format

Output $Q$ lines, each containing the answer for a corresponding query.

Sample Input and Output

Sample Input #1

3
1 1 1
2 0 2
3 1 1

Sample Output #1

1
8
4

Sample Input #2

3
4 1 1
5 2 3
5 0 3

Sample Output #2

6
4
24

Sample Input #3

4
7 2 5
6 1 1
10 4 5
6 2 2

Sample Output #3

6
20
5
4

Notes

[Data Range and Constraints]

• For $100\%$ of the data, $1 \le Q \le 10^5$, $1 \le K_i, M_i \le 150$, $0 \le L_i \le K_i$.

[Hint and Disclaimer]

Feel free to hack the custom Special Judge by sending private messages or posting on the forum.

This problem is translated from COCI 2015-2016 #7 Task 5 Prosti.

The score for this problem is set according to the original COCI, with a maximum of $140$.

见题面 Input 部分

见题面 Output 部分