Problem Description

There are $Q$ queries. In each query, you are given positive integers $K, L, M$. Define the set of all happy numbers as $\{x \mid x \le M \text{ or } x \text{ is prime}\}$.

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 \le 10^7$ exists, 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 line being the answer to the corresponding query.

3
1 1 1
2 0 2
3 1 1

1
8
4

3
4 1 1
5 2 3
5 0 3

6
4
24

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

6
20
5
4

Hint

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$.

Hints and Notes

You are welcome to hack the self-written Special Judge by private message or by making a post.

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

The score of this problem follows the original COCI settings, with a full score of $140$.

Translated by ChatGPT 5