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

using namespace std;

const int VMAX = 1e6;

vector <int> prime;

void ciurul()
{
    bitset <VMAX+1> c;
    for (int i = 2; i * i <= VMAX; i++)
    {
        if (!c[i])
        {
            for (int mult = i * i; mult <= VMAX; mult += i)
            {
                c[mult] = 1;
            }
        }
    }
    for (int i = 2; i <= VMAX; i++)
    {
        if (!c[i])
        {
            prime.push_back(i);
        }
    }
}

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

int main()
{
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    ciurul();
    int q;
    in >> q;
    for (int iq = 0; iq < q; iq++)
    {
        long long a, b;
        in >> a >> b;
        vector <long long> dp;
        descompunere(b, dp);
        int ndp = (int)dp.size();
        long long nr = 0;
        for (int i = 0; i < (1 << ndp); i++)
        {
            int nrb1 = 0;
            long long div = 1;
            for (int j = 0; j < ndp; j++)
            {
                if (i & (1 << j))///j apartine multimii codificate de i
                {
                    nrb1++;
                    div *= dp[j];
                }
            }
            if (nrb1 % 2 == 0)///multiplii lui div corespund unei submultimi cu nr par de div
            {
                nr += a / div;///adunam nr. de multipli ai lui div mai mici sau egali cu a
            }
            else
            {
                nr -= a / div;///scadem ...
            }
        }
        out << nr << "\n";
    }
    in.close();
    out.close();
    return 0;
}