{"raw_statement":[{"iden":"statement","content":"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.\n\nYou 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_)."},{"iden":"input","content":"The first line contains one integer _t_ (1 ≤ _t_ ≤ 30000) — the number of queries to process.\n\nThen _t_ lines follow. _i_\\-th line contains three integers _x_, _p_ and _k_ for _i_\\-th query (1 ≤ _x_, _p_, _k_ ≤ 106)."},{"iden":"output","content":"Print _t_ integers, where _i_\\-th integer is the answer to _i_\\-th query."},{"iden":"examples","content":"Input\n\n3\n7 22 1\n7 22 2\n7 22 3\n\nOutput\n\n9\n13\n15\n\nInput\n\n5\n42 42 42\n43 43 43\n44 44 44\n45 45 45\n46 46 46\n\nOutput\n\n187\n87\n139\n128\n141"}],"translated_statement":[{"iden":"statement","content":"我们定义 #cf_span[L(x, p)] 为一个无限整数序列 #cf_span[y]，满足 #cf_span[gcd(p, y) = 1] 且 #cf_span[y > x]（其中 #cf_span[gcd] 表示两个整数的最大公约数），并将这些整数按升序排列。序列 #cf_span[L(x, p)] 的元素是 #cf_span[1]-索引的；例如，#cf_span[9]、#cf_span[13] 和 #cf_span[15] 分别是 #cf_span[L(7, 22)] 的第一个、第二个和第三个元素。\n\n你需要处理 #cf_span[t] 个查询。每个查询由三个整数 #cf_span[x]、#cf_span[p] 和 #cf_span[k] 表示，该查询的答案是 #cf_span[L(x, p)] 的第 #cf_span[k] 个元素。\n\n第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 30000]) —— 需要处理的查询数量。\n\n接下来 #cf_span[t] 行，每行包含三个整数 #cf_span[x]、#cf_span[p] 和 #cf_span[k]，表示第 #cf_span[i] 个查询 (#cf_span[1 ≤ x, p, k ≤ 106])。\n\n请输出 #cf_span[t] 个整数，其中第 #cf_span[i] 个整数是第 #cf_span[i] 个查询的答案。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 30000]) —— 需要处理的查询数量。接下来 #cf_span[t] 行，每行包含三个整数 #cf_span[x]、#cf_span[p] 和 #cf_span[k]，表示第 #cf_span[i] 个查询 (#cf_span[1 ≤ x, p, k ≤ 106])。"},{"iden":"output","content":"请输出 #cf_span[t] 个整数，其中第 #cf_span[i] 个整数是第 #cf_span[i] 个查询的答案。"},{"iden":"examples","content":"输入37 22 17 22 27 22 3输出91315输入542 42 4243 43 4344 44 4445 45 4546 46 46输出18787139128141"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ L(x, p) $ be the infinite sequence of integers $ y $ such that $ y > x $ and $ \\gcd(y, p) = 1 $, sorted in ascending order. The sequence is 1-indexed.\n\n**Constraints**  \n1. $ 1 \\le t \\le 30000 $  \n2. For each query: $ 1 \\le x, p, k \\le 10^6 $\n\n**Objective**  \nFor each query $ (x, p, k) $, compute the $ k $-th element of $ L(x, p) $, i.e., the $ k $-th smallest integer $ y > x $ such that $ \\gcd(y, p) = 1 $.","simple_statement":null,"has_page_source":false}