List Of Integers

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
template <class T>
void read(T &val) { T x = 0; T bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int mod=1e9+7;
const int maxn = 1e6+10;
int cnt = 0;
int b[maxn];
void divide(int p){
    cnt=0;
    for(int i=2;i*i<=p;i++){
        if(p%i==0){
            b[++cnt]=i;
            while(p%i==0) p/=i;
        }
    }
    if(p>1) b[++cnt]=p;
}

LL num = 0;
void dfs(LL x,int dep,int times){
    if(dep>cnt){
        if(times&1) num-=x;
        else num+=x;
        return;
    }
    dfs(x,dep+1,times);
    dfs(x/b[dep],dep+1,times+1);
}

LL cal(LL x){
    num = 0;
    dfs(x,1,0);
    return num;
}

int main(){
    int t;read(t);
    while(t--){
        LL x,p,k,l,r,ans=0;
        read(x);read(p);read(k);
        divide(p);
        k+=cal(x);
        l = x+1;r = 1e9;
        while(l<=r){
            LL mid=l+r>>1;
            if(cal(mid)>=k){
                ans=mid;r=mid-1;
            }
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}