题目描述

Process $Q$ queries. The $i$-th query is as follows:

• Given integers $L_i$, $R_i$, and $K_i$, find the $K_i$-th smallest positive integer $x$ such that $x$ does not divide any of the integers from $L_i$ to $R_i$ (inclusive).

输入格式

The input is given in the following format:

$$\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$
• All input values are integers.

输出格式

Output $Q$ lines. On the $i$-th line, output the answer for the $i$-th query.

3
10 11 5
12345 23456 789
1 200000 200000

8
23629
400000