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
import sys,math,itertools
from collections import Counter,deque,defaultdict
from bisect import bisect_left,bisect_right 
from heapq import heappop,heappush,heapify, nlargest
from copy import deepcopy
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_1(): return list(map(lambda x:int(x)-1, sys.stdin.readline().split()))
def inps(): return sys.stdin.readline()
def inpsl(x): tmp = sys.stdin.readline(); return list(tmp[:x])
def err(x): print(x); exit()

MAX = 10**6+10
ele = [[] for _ in range(MAX+10)]
for i in range(2,MAX):
    if ele[i]:continue
    for j in range(i,MAX,i):
        ele[j].append(i)

def lcm(a,b): return a*b//math.gcd(a,b)
for _ in range(inp()):
    x,p,k = inpl()
    ok = 10**20
    ng = 1
    def houjo(x):
        ln = len(ele[p])
        su = 0
        for mask in range(1<<ln):
            l = 1; bit = 0
            for i in range(ln):
                if (mask>>i)&1:
                    l = lcm(l,ele[p][i]); bit += 1
            if bit==0: continue
            elif bit%2: su += x//l
            else: su -= x//l
        # print(x,su)
        return x-su
    X = houjo(x)
    def sol(y): #x+1...yまでの整数の中でpと互いに素であるものがk個以上あるか
        return houjo(y)-X >= k
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if sol(mid): ok = mid
        else: ng = mid
    print(ok)