#include <fstream>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

bool not_prime[1000001];
int v[1000001], fact[31];

inline void getPrimes(int n, int& m)
{   int i, j;
    for (i=4;i<=n;i+=2)
        not_prime[i]=true;
    for (i=3;i*i<=n;i+=2)
        if (!not_prime[i])
            for (j=i*i;j<=n;j+=i)
                not_prime[j]=true;
    m=0;
    for (i=2;i<=n;++i)
        if (!not_prime[i])
            v[++m]=i;
}

int main()
{   ios::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);
    int n, Q, k, i, cnt, j, sign;
    long long a, b, ans, prod;
    getPrimes(1000000, n);
    fin>>Q;
    while (Q--)
    {   fin>>a>>b;
        k=0;
        for (i=1;v[i]*v[i]<=b && i<=n;++i)
            if (!(b%v[i]))
            {   fact[++k]=v[i];
                while (!(b%v[i]))
                    b/=v[i];
            }
        if (b!=1)
            fact[++k]=b;
        ans=0;
        for (i=1;i<(1<<k);++i)
        {   cnt=0;
            prod=1;
            for (j=0;j<k;++j)
                if (i&(1<<j))
                {   prod*=fact[j+1];
                    ++cnt;
                }
            if (cnt%2)
                sign=1;
            else
                sign=-1;
            ans+=sign*(a/prod);
        }
        fout<<a-ans<<'\n';
    }
    fin.close();
    fout.close();

    return 0;
}