#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector<int> prim;
int n;
long long A,b;
vector<int> fact;
bitset<1000003> a;
inline void prelucru(long long x)
{
    int d=0;
    while (d<prim.size() && prim[d]*prim[d]<=x)
    {
        long long aux=prim[d];
        if (x%aux==0) fact.push_back(aux),x/=aux;
        while (x%aux==0) x/=aux;
        d++;
    }
    if (x>1) fact.push_back(x);
}
int main()
{
    fin>>n;
    for (int i=2; i<=1000000; i++)
    {
        if (a[i]==0)
        {
            prim.push_back(i);
            for (int j=2*i; j<=1000000; j+=i)
                a[j]=1;
        }
    }
    while (n--)
    {
        fin>>A>>b;
        fact.clear();
        prelucru(b);
        long long rez=0;
        int lung=fact.size();
        int m=(1<<lung);
        for (int i=1; i<m; i++)
        {
            int nr=0;
            long long prod=1;
            for (int j=0; j<lung; j++)
            {
                if (i&(1<<j))
                {
                    prod=1LL*prod*fact[j];
                         nr++;
                }
            }
            if (nr%2==0) nr=-1;
            else nr=1;
            rez=rez+1LL*nr*(A/prod);
        }
        fout<<A-rez<<'\n';
    }
    return 0;
}