← 返回题目列表

Codeforces · 920/G

G. 整数列表

中文机器翻译题面 查看原题

让我们将整数 y 的无限序列表示为 L(x, p),使得 gcd(p, y) = 1 且 y > x(其中 gcd 是两个整数的最大公约数),按升序排序。 L(x, p) 的元素是 1 索引的;例如,9、13和15分别是L(7, 22)的第一、第二和第三个元素。

您必须处理 t 个查询。每个查询由三个整数 x、p 和 k 表示,该查询的答案是 L(x, p) 的第 k 个元素。

输入

第一行包含一个整数 t (1 ≤ t ≤ 30000) — 要处理的查询数。

然后是 t 行。第 i 行包含第 i 个查询的三个整数 x、p 和 k (1 ≤ x, p, k ≤ 106)。

输出

打印 t 个整数,其中第 i 个整数是第 i 个查询的答案。

示例

输入 #1

3
7 22 1
7 22 2
7 22 3

输出 #1

9
13
15

输入 #2

5
42 42 42
43 43 43
44 44 44
45 45 45
46 46 46

输出 #2

187
87
139
128
141