说明

处理 $Q$ 个查询。第 $i$ 个查询如下：

• 给定整数 $L_i$、$R_i$ 和 $K_i$，找出第 $K_i$ 小的正整数 $x$，使得 $x$ 不整除 $L_i$ 到 $R_i$（含）之间的任何整数。

输入格式

输入以如下格式给出：

$$\begin{aligned} &Q \\ &L_1 \ R_1 \ K_1 \\ &\vdots \\ &L_Q \ R_Q \ K_Q \end{aligned}$$

• $1 \leq Q \leq 100,000$
• $1 \leq L_i \leq R_i \leq 200,000$
• $1 \leq K_i \leq 200,000$
• 所有输入值均为整数。

输出格式

输出 $Q$ 行。在第 $i$ 行输出第 $i$ 个查询的答案。

3
10 11 5
12345 23456 789
1 200000 200000

8
23629
400000

提示

翻译由 DeepSeek V3.2 完成