让我们将整数 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