{"problem":{"name":"G. List Of Integers","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF920G"},"statements":[{"statement_type":"Markdown","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_).\n\n## Input\n\nThe 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).\n\n## Output\n\nPrint _t_ integers, where _i_\\-th integer is the answer to _i_\\-th query.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","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] 个查询的答案。\n\n## Input\n\n第一行包含一个整数 #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])。\n\n## Output\n\n请输出 #cf_span[t] 个整数，其中第 #cf_span[i] 个整数是第 #cf_span[i] 个查询的答案。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF920G","tags":["binary search","bitmasks","brute force","combinatorics","math","number theory"],"sample_group":[["3\n7 22 1\n7 22 2\n7 22 3","9\n13\n15"],["5\n42 42 42\n43 43 43\n44 44 44\n45 45 45\n46 46 46","187\n87\n139\n128\n141"]],"created_at":"2026-03-03 11:00:39"}}