/*
 * =====================================================================================
 *
 *       Filename:  920G.cpp
 *
 *    Description:  codeforces 920G: List Of Integers
 *
 *        Version:  1.0
 *        Created:  2018年02月07日 12時48分22秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  lionking
 *   Organization:  None
 *
 * =====================================================================================
 */

#include <cstdio>
#include <vector>


using namespace std;


/*****************************************************************************************
 * Generate prime table
 * Given a threshold, this function will generate list all primes less than the threshold.
 *
 * Parameter:
 * 1. prime: the resultant prime table
 * 2. limit: the given threshold
 *
 * Return value:
 * Number of primes in the generated prime table
 *****************************************************************************************/
template <typename T>
size_t GeneratePrime(std::vector<T> &prime, const size_t limit)
{
    prime.clear();
    std::vector<bool> check(limit, true);

	/* check[i] = false: prime else not prime	*
	* mask all even number to be not prime		*/
	check[0] = check[1] = false;
	for (int i = 4; i < limit; i += 2) check[i] = false;
	for (int i = 9; i < limit; i += 3) check[i] = false;

    prime.push_back(2);
    prime.push_back(3);
	for (int i = 5; i<limit; i += 2) {
		if (check[i]) {
			/* is prime */
			prime.push_back(i);
			for (int j = i*i; j<limit; j += i) { check[j] = false; }
		}
	}

    return prime.size();
}


/**********************************************************************************************
 * Euler Totient Function : phi(n)
 * This function will generate a table containing phi(i)
 *
 * Parameter list:
 * 1. phi: resultant table containing phi(i)
 * 2. limit: threshold. Only positive integers less than this threshold will generate phi(i)
 * 3. prime: prime tables with all primes less than the given threshold (namely, 2nd parameter)
 *
 * Return value:
 * None
 **********************************************************************************************/
template <typename T>
void euler_totient(std::vector<T>& phi, const size_t limit, const std::vector<T>& prime)
{
    const auto primecount = prime.size();
    phi.clear();
    phi.resize(limit, 0);
	phi[1] = phi[2] = 1;

	for(int i=3; i<=limit; ++i){
		int temp = phi[i] = i;
		for(int j=0; (j<primecount) && (prime[j]*prime[j]<=temp); ++j){
			if(!(temp%prime[j])){
				phi[i] = (phi[i]/prime[j])*(prime[j]-1);
				while(!(temp%prime[j]))
					temp /= prime[j];
			}
		}
		if(temp!=1)
			phi[i] = (phi[i]/temp)*(temp-1);
	}
}


/****************************************************************************************************
 * Prime Factorization
 * Given a positive integer n = p1 ^ k1 * p2 ^ k2 * ... * pm ^ km, where p1, p2, ... , pm are primes,
 * this function will return the list {p1, p2, ... , pm}
 *
 * Parameters:
 * 1. prime: prime table
 * 2. value: the given value for prime factorization (namely, n described above)
 *
 * Return value:
 * Required prime list (namely, {k1, k2, ... , km} described above)
 ****************************************************************************************************/
template <typename T>
std::vector<T> factorization(const std::vector<T>& prime, const T& value)
{
    std::vector<T> result;

    T curr = value;
    for (size_t i = 0; i < prime.size(); ++i) {
        if (prime[i] * prime[i] > curr) { break; }
        if ((curr % prime[i]) == 0) {
            result.push_back(prime[i]);
            while ((curr % prime[i]) == 0) { curr /= prime[i]; }
        }
    }
    if (curr > static_cast<T>(1)) { result.push_back(curr); }

    return result;
}


/******************************************************************************************************************
 * Given two positive integers n and x, where x = p1 ^ k1 * p2 ^ k2 * ... * pm ^ km, and p1, p2, ... pm are primes,
 * this function will return the number of values y that y <= n and gcd(y, x) = 1, where
 * gcd(y, x) is the greatest common divisor of y and x.
 * Namely, it will find how many values are less than n are coprime with x.
 *
 * Example: Let n = 12 and x = 6, the result is 4 ({1, 5, 7, 11})
 * Note: When n = x, the result is equal to phi(n), where phi is Euler Totient Function.
 *
 * Parameters:
 * 1. prime: prime list {p1, p2, ... , pm}
 * 2. value: n
 *
 * Return value:
 * Number of values that are less than n and coprime with x.
 ******************************************************************************************************************/
template <typename T>
T coprimeCount(const std::vector<T>& prime, const T value)
{
    T ans = 0;

    // Use Inclusion-Exclusion principle
    const T bitmask = (static_cast<T>(1) << prime.size());
    for (T bit = 0; bit < bitmask; ++bit) {
        T curr = 1, flag = 1;
        // Let bit = b1 b2 ... bm, where bit is in [0, 2^ps), ps = prime.size()
        // bi = 1, if currently we need to process prime[i]; otherwise skip prime[i]
        for (size_t i = 0; i < prime.size(); ++i) {
            if ((bit >> i) & 1) { // bi = 1
                curr *= prime[i];
                flag *= -1;
            }
        }
        // flag = 1 when there is even number of bi = 1
        // otherwise, flag = -1
        ans += flag * (value / curr);
    }

    // Example: x = 6 = 2 ^1 * 3 ^1
    // prime = {2, 3}, and bit will be {00, 01, 10, 11}
    // bit = 00: ans +=   1  * (value / 1)
    // bit = 01: ans += (-1) * (value / 3)
    // bit = 10: ans += (-1) * (value / 2)
    // bit = 11: ans +=   1  * (value / (2 * 3))

    return ans;
}


/******************************************************************************************************************
 * Given two positive integers n and x, where x = p1 ^ k1 * p2 ^ k2 * ... * pm ^ km, and p1, p2, ... pm are primes,
 * this function will return the number of values y that y <= n and gcd(y, x) = 1, where
 * gcd(y, x) is the greatest common divisor of y and x.
 * Namely, it will find how many values are less than n are coprime with x.
 *
 * Example: Let n = 12 and x = 6, the result is 4 ({1, 5, 7, 11})
 * Note: When n = x, the result is equal to phi(n), where phi is Euler Totient Function.
 *
 * Parameters:
 * 1. prime: prime list {p1, p2, ... , pm}
 * 2. value: n
 * 3. x: as the x described above
 * 4. phi_x: phi(x), where phi is Euler Totient function.
 *
 * Return value:
 * Number of values that are less than n and coprime with x.
 ******************************************************************************************************************/
template <typename T>
T coprimeCount(const std::vector<T>& prime, const T value, const T x, const T phi_x)
{
    return coprimeCount(prime, value % x) + (value / x) * phi_x;
}


// return the kth value that is relative prime to p and larger than x
int kthValue(const std::vector<int>& prime, const int x, const int p, int k)
{
#define INF 0x3fffffff

    const auto ex_prime = factorization(prime, p);
    k += coprimeCount(ex_prime, x);

    int left = 1, right = INF;
    // binary search
    while (left < right) {
        const auto middle = (left + right) / 2;
        if (coprimeCount(ex_prime, middle) < k) {
            left = middle + 1;
        }
        else {
            right = middle;
        }
    }

    return right;
}


// return the kth value that is relative prime to p and larger than x
int kthValue(const std::vector<int>& prime, const std::vector<int>& phi, const int x, const int p, int k)
{
#define INF 0x3fffffff

    const auto ex_prime = factorization(prime, p);
    k += coprimeCount(ex_prime, x, p, phi[p]);

    int left = 1, right = INF;
    // binary search
    while (left < right) {
        const auto middle = (left + right) / 2;
        if (coprimeCount(ex_prime, middle, p, phi[p]) < k) {
            left = middle + 1;
        }
        else {
            right = middle;
        }
    }

    return right;
}


int main(int argc, char *argv[])
{
#define MAX_VALUE 1000000

    std::vector<int> prime, phi;
    const auto prime_count = GeneratePrime(prime, MAX_VALUE);
    euler_totient(phi, MAX_VALUE, prime);

    int t;
    while (scanf("%d", &t) == 1) {
        for (int i = 0; i < t; ++i) {
            int x, p, k;
            if (scanf("%d %d %d", &x, &p, &k) == 3) {
                printf("%d\n", kthValue(prime, x, p, k));
                //printf("%d\n", kthValue(prime, phi, x, p, k)); // much slower...
            }
        }
    }

    return 0;
}