Let's denote as *L*(*x*, *p*) an infinite sequence of integers *y* such that *gcd*(*p*, *y*) = 1 and *y* &gt; *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*).
The 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* ≤ 10<sup class="upper-index">6</sup>).
none
3
7 22 1
7 22 2
7 22 3
9
13
15
5
42 42 42
43 43 43
44 44 44
45 45 45
46 46 46
187
87
139
128
141
from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fast_prime_factorization(n):
    d = [(i + 1) % 2 * 2 for i in range(n + 1)]
    d[0], d[1] = 0, 1
    for i in range(3, n + 1):
        if d[i]:
            continue
        for j in range(i, n + 1, 2 * i):
            if not d[j]:
                d[j] = i
    return d

def divisor(i):
    s = [1]
    cnt = defaultdict(lambda : 0)
    while i ^ pf[i]:
        cnt[pf[i]] += 1
        i //= pf[i]
    if i ^ 1:
        cnt[i] += 1
    for i in cnt.keys():
        l = len(s)
        y = []
        for j in range(1, cnt[i] + 1):
            y.append(pow(i, j))
        for j in range(l):
            sj = s[j]
            for y0 in y:
                s.append(y0 * sj)
    s.sort()
    return s

def f(u):
    dp = [0] * n
    dp[0] = 1
    v = 0
    for i in range(n):
        dpi = dp[i]
        si = s[i]
        if u < si:
            break
        v += u // si * dpi
        for j in s0[i]:
            dp[j] -= dpi
    return v

def binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        m = (c1 + c2 + 1) // 2
        if f(m) < k:
            c1 = m
        else:
            c2 = m
    m = max(m - 2, 0)
    while f(m) < k:
        m += 1
    return m

t = int(input())
pf = fast_prime_factorization(pow(10, 6) + 5)
ans = []
for _ in range(t):
    x, p, k = map(int, input().split())
    s = divisor(p)
    n = len(s)
    s0 = [[] for _ in range(n)]
    for i in range(n):
        si = s[i]
        for j in range(i + 1, n):
            if not s[j] % si:
                s0[i].append(j)
    c = f(p)
    c0 = f(x)
    d = (c0 + k - 1) // c
    k = (c0 + k - 1) % c + 1
    ans0 = p * d + binary_search(0, p + 1)
    ans.append(ans0)
sys.stdout.write("\n".join(map(str, ans)))