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
'''t=int(input())
s=[]
for i in range(t):
    n,k=int(input()),int(input())
    a=list(map(int,input().split()))
    b=0
    for i in a:
        if(i<=0):
            b+=1
    if(b>=k):
        s.append('YES')
    else:
        s.append('NO')
    
print("\n".join(map(str,s)))'''

'''def r(x):
    rev=0
    while(x):
        a=x%10
        x=x//10
        rev=a+rev*10
    return(rev)    
i,j,k=list(map(int,input().split()))
c=0
for x in range(i,j+1):
    if(abs(x-r(x))==k):
        c+=1
print(c)  '''

'''global no
no=0
k=5

def fun(n,k):
    if(n==0):
        return(None)
    no+=(k//2)    
    return(fun(n-1,(k//2)*3))    
n=int(input())         
print(fun(n,k))'''

'''t=int(input())
for i in range(t):
    n,m,s=list(map(int,input().split()))
    if(m>n):
        if(m%n==0):
            f=(m+1)%n
            print(s-f)
        else:
            f=m%n
            if(f>(n-s+1)):
                print(f-n+s-1)
            else:
                print(s+f-1)
    else:
          print(s+m-1)'''
         
'''a=(67,43,2,3,5)   
from functools import cmp_to_key          
n=list(map(str,a))
print(sorted(n,key=cmp_to_key(lambda x,y: 1 if((int(x+y) < int(y+x))) else -1   )   ))
'''

'''t=int(input())
for i in range(t):
    s=input()
    c=0
    a=set("chef")
    for i in range(0,len(s)-3):
        j=i+3
        if (a==set(s[i:j+1])):
            c+=1
    if(c==0):
        print("normal")
    else:
        print("lovely "+str(c))'''
        
'''t=int(input())
for i in range(t):
    n,m,x,k=list(map(int,input().split()))
    s=input()
    if(n>k or x*m<n):
        print("no")
    else:
        month=1
        o=0
        e=0
        while(month<=m ):
            y=0
            if(month%2!=0):
                if(s.count('O')-o>=x):
                    y=x
                    o+=x
                else:
                    y=s.count('O')-o
                    o+=s.count('O')-o
                n-=y
            elif(month%2==0):
                if(s.count('E')-e>=x):
                    y=x
                    e+=x
                else:
                    y=s.count('E')-e
                    e+=s.count('E')-e
                n-=y    
            month+=1
        if(n<=0):
            print("yes")
        else:
            print("no")'''

import sys
def gcd(a,b):
    if(b>a):
        gcd(b,a)
    elif(b==0):
        return(a)
    return(gcd(b,a%b))    
t=int(input())
for i in range(t):
    x,p,k=list(map(int,input().split()))
    l=[]
    for y in range(x+1,sys.maxsize):
        if(gcd(p,y)==1):
            k-=1
        if(k==0):
            print(y)
            break


































            
            
            
    
                    
                
        
    























        
      






        