题目描述

现有 $Q$ 组询问，每次给出正整数 $K,L,M$。定义全体高兴数的集合为 $\{x|x \le M$ 或 $x$ 为质数$\}$。

对于每次询问，求一个正整数 $i$，使得 $[i,i+K-1]$ 内恰好有 $L$ 个高兴数。如果不大于 $10^7$ 的 $i$ 值不存在，输出 $-1$。

输入格式

第一行，一个整数 $Q$。

接下来的 $Q$ 行，每行三个整数 $K_i,L_i,M_i$。

输出格式

输出 $Q$ 行，每行对应一次询问的答案。

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

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，$1 \le Q \le 10^5$，$1 \le K_i,M_i \le 150$，$0 \le L_i \le K_i$。

【提示与说明】

欢迎大家通过私信或发帖对自行编写的 Special Judge 进行 hack。

题目译自 COCI 2015-2016 #7 Task 5 Prosti。

本题分值按 COCI 原题设置，满分 $140$。