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
#include <bits/stdc++.h>

using namespace std;


vector<int> factorize(int x){
    vector<int> P;
    for(int i = 2; i*i <= x;i++){
        if (x % i == 0) {
                P.push_back(i);
                while(x % i == 0) x /= i;
        }
    }
    if (x > 1) P.push_back(x);
//    for (auto it : P) cout <<it <<" ";
//    cout << endl;
    return P;
}

int query(int x,vector<int> &V){
    int ans = 0;
    int N = V.size();
    for (int i = 0; i < (1<<N);i++){
        int temp = 1;
        int sgn = 1;
        for (int j = 0; j < N;j++){
            if ((i>>j)&1){
                temp *= V[j];
                sgn *= -1;
            }
        }
        ans += sgn*x/temp;
    }
    return ans;
}

int query(int x,int p){
    int cnt=0;
    for (int i = 1; i <= x;i++) if (__gcd(i,p) == 1) cnt++;
    return cnt;
}

int query(int x,int p,int i){
    int st = x,dr = 1e6,mid,rs = -1,C;
    vector<int> P = factorize(p);
    C = query(x,P);
    while (st <= dr - 1){
        int mid = (st + dr)/2;
        int val = query(mid,P) - C;
        //cout << mid<<" "<<val<<endl;
        if (val < i) st = mid + 1;
        else dr = mid;
    }
    while(query(st,p)- C == i) st--;
    return st + 1;

}

int main(){
    int T;
    cin >> T;
    while (T--){
        int x,p,i;
        cin >> x >> p >> i;
        cout <<query(x,p,i)<<endl;
    }
    return 0;
}
