P8036 [COCI 2015/2016 #7] Prosti

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

The first line contains an integer $Q$. The next $Q$ lines each contain three integers $K_i, L_i, M_i$.

Output $Q$ lines, each line being the answer to the corresponding query.

**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](https://www.luogu.com.cn/paste/rj308p4r) by private message or by making a post. **This problem is translated from [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 5 Prosti_.** **The score of this problem follows the original COCI settings, with a full score of $140$.** Translated by ChatGPT 5