#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

const int RMAX = 1e6;

vector <int> prime;

void ciurul()
{
    ///construieste prime = vector cu numerele prime <= 10^6
    bitset <RMAX+1> c;
    for (int d = 2; d * d <= RMAX; d++)
    {
        if (!c[d])
        {
            for (int m = d * d; m <= RMAX; m += d)
            {
                c[m] = 1;
            }
        }
    }
    for (int i = 2; i <= RMAX; i++)
    {
        if (!c[i])
        {
            prime.push_back(i);
        }
    }
}

void desc(long long x, vector <long long> &dp)
{
    int i = 0, np = (int)prime.size();
    while (i < np && (long long)prime[i] * prime[i] <= x)
    {
        if (x % prime[i] == 0)
        {
            dp.push_back(prime[i]);
            while (x % prime[i] == 0)
            {
                x /= prime[i];
            }
        }
        i++;
    }
    if (x != 1)
    {
        dp.push_back(x);
    }
}

long long nr_prime_cu(long long n, long long x)
{
    vector <long long> dp;
    desc(x, dp);
    int nd = (int)dp.size();
    long long nr = 0;
    ///generam multimile de indici
    ///(submultimi ale lui {0, 1,... nd-1})
    for (int multime = 0; multime < (1 << nd); multime++)
    {
        bool aduna = true;
        long long prod_dp = 1;
        for (int i = 0; i < nd; i++)
        {
            if (multime & (1 << i))///i apartine multime
            {
                aduna = (!aduna);
                prod_dp *= dp[i];
            }
        }
        if (aduna)
        {
            nr += n / prod_dp;
        }
        else
        {
            nr -= n / prod_dp;
        }
    }
    return nr;
}

int main()
{
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    ciurul();
    int t;
    in >> t;
    for (int i = 0; i < t; i++)
    {
        long long n, x;
        in >> n >> x;
        out << nr_prime_cu(n, x) << "\n";
    }
    in.close();
    out.close();
    return 0;
}