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 math import sqrt


def c(N):
    sqrt_N = int(sqrt(N))
    indexes = [q for q in range(1, 1 + sqrt_N))
    for k in range(sqrt_N, 0, -1):
        if indexes[-1] != N // k: indexes.append(N // k)
    res = {}
    for n in indexes:
        tmp = n ** 2
        if 1 < n:
            sqrt_n = int(sqrt(n))
            for l in range(1, sqrt_n + 1):
                tmp -= res[l] * (n // l - n // (l + 1))
            for d in range(2, 1 + n // (1 + sqrt_n)):
                tmp -= res[n // d]
        res[n] = tmp
    return res[N]


L = 3000000
phi = [i for i in range(L + 1)]
for i in range(2, L + 1):
    if phi[i] == i:
        for j in range(i, L + 1, i): phi[j] = phi[j] // i * (i - 1)

for i in range(1, L + 1): phi[i] += phi[i - 1]


def cc(N, M):
    if N > M:
        N, M = M, N
    return c(N) + phi[M] - phi[N]


def calc(N, M):
    res = cc(N, M)
    if N > 1: res -= cc(N - 1, M)
    return res


t = int(input())
for _ in range(t):
    x, p, k = map(int, input().split())
    ans = L
    shift = 2097152
    qq = calc(p, x)
    while shift > 0:
        if ans - shift >= x:
            if calc(p, ans - shift) - qq >= k: ans -= shift
        shift /= 2
    print(ans)
