G. List Of Integerstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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).InputThe 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).OutputPrint t integers, where i-th integer is the answer to i-th query.ExamplesInput37 22 17 22 27 22 3Output91315Input542 42 4243 43 4344 44 4445 45 4546 46 46Output18787139128141
Input37 22 17 22 27 22 3
Output91315
['binary search', 'bitmasks', 'brute force', 'combinatorics', 'math', 'number theory', '*2200']