CF920G.List Of Integers

Let's denote as L(x, p) an infinite sequence of integers y such that gcd(p, y) = 1 and y > x (where gcd is the greatest common divisor of two integer numbers), sorted in ascending order. The elements of L(x, p) are 1-indexed; for example, 9, 13 and 15 are the first, the second and the third elements of L(7, 22), respectively.

You have to process t queries. Each query is denoted by three integers x, p and k, and the answer to this query is k-th element of L(x, p).

我们用 $L(x, p)$ 表示一个无限整数序列 $y$，其中满足 $\gcd(p, y) = 1$ 且 $y > x$（$\gcd$ 表示两个整数的最大公约数），并按升序排列。$L(x, p)$ 的元素采用 1-索引；例如，$9$、$13$ 和 $15$ 分别是 $L(7, 22)$ 的第 $1$、第 $2$ 和第 $3$ 个元素。

你需要处理 $t$ 个查询。每个查询由三个整数 $x$、$p$ 和 $k$ 给出，该查询的答案即为 $L(x, p)$ 的第 $k$ 个元素。

The first line contains one integer t (1 ≤ t ≤ 30000) — the number of queries to process.

Then t lines follow. i-th line contains three integers x, p and k for i-th query (1 ≤ x, p, k ≤ 106).

第一行包含一个整数 $t$（$1 \leq t \leq 30000$）—— 表示需要处理的查询数量。

接下来是 $t$ 行。第 $i$ 行包含三个整数 $x$、$p$ 和 $k$，对应第 $i$ 个查询（$1 \leq x, p, k \leq 10^6$）。

Print t integers, where i-th integer is the answer to i-th query.

输出 t 个整数，其中第 i 个整数是第 i 个查询的答案。